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 (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.
Leaders enjoy math challenges, so they wonder how many ways can they organize all students on a line. Can you help them with that?
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.
Output one integer, the number of ways the leaders can organize the students on a line modulo $10^9 + 7$.
For the first case, there are only 6 ways to organize the students:
## Input
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.
## Output
Output one integer, the number of ways the leaders can organize the students on a line modulo $10^9 + 7$.
[samples]
## Note
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
**Definitions**
Let $ N, S \in \mathbb{Z}^+ $ with $ 1 \leq N, S \leq 15 $.
Let $ \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.
Let $ W, H \in \mathbb{Z}^+ $ with $ 1 \leq W, H \leq 100 $.
Let $ 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) $.
**Transformations**
For a tile $ T_i \in \mathcal{T} $, define transformation functions $ f_t : \mathbb{C}^{S \times S} \to \mathbb{C}^{S \times S} $:
- $ f_0(T) = T $ (identity)
- $ f_1(T) $: 90° clockwise rotation
- $ f_2(T) $: 180° rotation
- $ f_3(T) $: 270° clockwise rotation (or 90° counterclockwise)
- $ f_4(T) $: flip across vertical axis (left-right)
- $ f_5(T) $: flip across horizontal axis (top-bottom)
**Objective**
Construct 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\} $:
The 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} $.
Output $ Q_{\text{final}} $ as $ H \cdot S $ lines, each containing $ W \cdot S $ characters.