Knights of the Round Table

Time limit3sMemory limit256 MB

Summary

Count distinct final seat assignments over all entry orders when each remaining knight walks clockwise to the first free seat, modulo 1e9+7.

Level: Hard8 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

K knights sit at seats 1..K around a circle. The first D distracted knights already sat (knight assigned seat A is on seat B). Each remaining knight enters, tries his own seat, and if it is taken walks clockwise to the first free seat. Count distinct final seatings over all entry orders of the remaining knights, modulo 10^9+7.

Input

Several test cases. Each has K, D, then D lines with A and B meaning the knight assigned seat A sat on seat B.

Output

For each test case, print the number of distinct final distributions modulo 10^9+7.

Examples7

Example 1
Input
```
3 1
1 2
```
Expected output
```
2
```
Example 2
Input
```
5 4
5 5
1 2
2 3
3 4
```
Expected output
```
1
```
Example 3
Input
```
8 3
3 3
4 8
2 4
```
Expected output
```
2
```
Example 4
Input
```
4 1
1 1
```
Expected output
```
1
```
Example 5
Input
```
4 1
1 2
```
Expected output
```
4
```
Example 6
Input
```
6 2
1 3
2 4
```
Expected output
```
18
```
Example 7
Input
```
3 1
1 2
5 4
5 5
1 2
2 3
3 4
```
Expected output
```
2
1
```