{"problem":{"name":"G. Great dinner","description":{"content":"UNAL is about to restart classes and the leaders of the algorithms group want to receive all its members with a great dinner in the university campus central dining room. The group has $N$ members (e","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10270G"},"statements":[{"statement_type":"Markdown","content":"UNAL is about to restart classes and the leaders of the algorithms group want to receive all its members with a great dinner in the university campus central dining room.\n\nThe group has $N$ members (excluding the leaders) numbered from $1$ to $N$ and the leaders want to organize them in a row before entering the dining room, in order to avoid any disorder. However, some students enjoy teasing others. In particular, there are $M$ bullies and $M$ victims, all of these $2 times M$ students are different. Each bully annoys exactly one victim and each victim is being bullied by exactly one bully. To make dinner a great time for everyone, the leaders want to ensure that if student A annoys student B, B must not be ahead of A in the line.\n\nLeaders enjoy math challenges, so they wonder how many ways can they organize all students on a line. Can you help them with that?\n\nThe first line contains two integers $N$ $(1 <= N <= 10^5)$ and $M$ $(0 <= 2 times M <= m i n (2 times 10^3, N))$ separated by a space — The number of students, and the number of bullies and victims, respectively.\n\nEach of the following $M$ lines will contain two integers $A$ and $B$ $(1 <= A, B <= N)$ separated by a space, which means that student $B$ must not be ahead of $A$ in the line. It is guaranteed that each, $A$ and $B$, appears at most once in the input.\n\nOutput one integer, the number of ways the leaders can organize the students on a line modulo $10^9 + 7$.\n\nFor the first case, there are only 6 ways to organize the students: \n\n## Input\n\nThe first line contains two integers $N$ $(1 <= N <= 10^5)$ and $M$ $(0 <= 2 times M <= m i n (2 times 10^3, N))$ separated by a space — The number of students, and the number of bullies and victims, respectively.Each of the following $M$ lines will contain two integers $A$ and $B$ $(1 <= A, B <= N)$ separated by a space, which means that student $B$ must not be ahead of $A$ in the line. It is guaranteed that each, $A$ and $B$, appears at most once in the input.\n\n## Output\n\nOutput one integer, the number of ways the leaders can organize the students on a line modulo $10^9 + 7$.\n\n[samples]\n\n## Note\n\nFor the first case, there are only 6 ways to organize the students:   1 2 3 4  1 3 2 4  1 3 4 2  3 1 2 4  3 1 4 2  3 4 1 2","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, S \\in \\mathbb{Z}^+ $ with $ 1 \\leq N, S \\leq 15 $.  \nLet $ \\mathcal{T} = \\{ T_0, T_1, \\dots, T_{N-1} \\} $ be a set of $ N $ Character Tiles, where each $ T_i $ is an $ S \\times S $ matrix over a character alphabet.  \n\nLet $ W, H \\in \\mathbb{Z}^+ $ with $ 1 \\leq W, H \\leq 100 $.  \nLet $ Q $ be a $ H \\times W $ grid of tile specifications, where each entry $ Q_{h,w} = (i, t) $ with $ i \\in \\{0, \\dots, N-1\\} $, $ t \\in \\{0, 1, 2, 3, 4, 5\\} $, specifying the tile index and transformation to apply at position $ (h, w) $.  \n\n**Transformations**  \nFor a tile $ T_i \\in \\mathcal{T} $, define transformation functions $ f_t : \\mathbb{C}^{S \\times S} \\to \\mathbb{C}^{S \\times S} $:  \n- $ f_0(T) = T $ (identity)  \n- $ f_1(T) $: 90° clockwise rotation  \n- $ f_2(T) $: 180° rotation  \n- $ f_3(T) $: 270° clockwise rotation (or 90° counterclockwise)  \n- $ f_4(T) $: flip across vertical axis (left-right)  \n- $ f_5(T) $: flip across horizontal axis (top-bottom)  \n\n**Objective**  \nConstruct the final $ (H \\cdot S) \\times (W \\cdot S) $ Character Quilt $ Q_{\\text{final}} $, such that for each $ h \\in \\{0, \\dots, H-1\\} $, $ w \\in \\{0, \\dots, W-1\\} $:  \nThe subgrid at rows $ [h \\cdot S : (h+1) \\cdot S - 1] $, columns $ [w \\cdot S : (w+1) \\cdot S - 1] $ is $ f_{t}(T_i) $, where $ (i, t) = Q_{h,w} $.  \n\nOutput $ Q_{\\text{final}} $ as $ H \\cdot S $ lines, each containing $ W \\cdot S $ characters.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10270G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}