원탁의 기사들

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

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

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