원탁의 기사들

시간 제한3초메모리 제한256 MB

요약

남은 기사가 임의의 순서로 입장해 자기 자리부터 시계 방향으로 첫 빈자리에 앉을 때 가능한 최종 배치 수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 조합론, 수학
정답자: 아직 제출이 없습니다

문제

K명의 기사가 원형 좌석 1..K에 앉는다. 처음 D명은 자리를 잘못 앉았고, 나머지는 번호 순으로 들어와 자기 자리가 비어 있으면 그 자리에, 아니면 시계 방향으로 첫 빈 자리에 앉는다. 남은 기사의 입장 순서에 따라 최종 배치가 달라질 수 있다. D명이 앉은 뒤 가능한 서로 다른 최종 배치 수를 10^9+7로 나눈 나머지를 구하라.

입력

여러 테스트 케이스가 주어진다. 각 케이스는 K, D와 D줄의 (A,B)로 구성된다. A번 기사가 B번 좌석에 앉았음을 뜻한다.

출력

각 테스트 케이스마다 서로 다른 최종 배치 수를 한 줄에 출력한다.

예제7

예제 1
입력
```
3 1
1 2
```
예상 출력
```
2
```
예제 2
입력
```
5 4
5 5
1 2
2 3
3 4
```
예상 출력
```
1
```
예제 3
입력
```
8 3
3 3
4 8
2 4
```
예상 출력
```
2
```
예제 4
입력
```
4 1
1 1
```
예상 출력
```
1
```
예제 5
입력
```
4 1
1 2
```
예상 출력
```
4
```
예제 6
입력
```
6 2
1 3
2 4
```
예상 출력
```
18
```
예제 7
입력
```
3 1
1 2
5 4
5 5
1 2
2 3
3 4
```
예상 출력
```
2
1
```