407237: GYM102700 G Great dinner

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 \leq N \leq 10^{5})$$$ and $$$M$$$ $$$(0 \leq 2 \times M \leq min(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 \leq A, B \leq 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$$$.

4 2
2 1
4 3

6

4 1
1 3

12

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