{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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."},{"iden":"output","content":"Output one integer, the number of ways the leaders can organize the students on a line modulo $10^9 + 7$."},{"iden":"examples","content":"Input4 2\n2 1\n4 3\nOutput6\nInput4 1\n1 3\nOutput12\n"},{"iden":"note","content":"For 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 "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":"Given N square tiles of size S×S, and a W×H grid of tile slots, each slot specifies a tile index and a transformation (0 to 5). Apply the transformation to each tile and arrange them in the grid to form a final quilt. Print the full quilt.","has_page_source":false}