14892번 - 좋은 순열의 개수

문제

크기가 M인 두 배열 X와 V, 정수 N이 주어졌을 때, 아래와 같은 조건을 만족하는 길이가 N인 순열 P의 개수를 구하는 프로그램을 작성하시오. 배열 방 번호는 1번부터 시작한다.

• 순열 P는 1부터 N까지의 수가 한 번씩 등장하는 수열이다.
• i < j이고, P[i] > j, P[j] > i인 (i, j)쌍이 적어도 하나 존재한다.
• 모든 1 ≤ i ≤ M에 대해서, P[X[i]] = V[i] 이다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 둘째 줄부터 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 N과 M(1 ≤ N ≤ 10⁹, 0 ≤ M ≤ 10⁴)가 주어진다. 둘째 줄부터 M개의 줄에는 배열 X와 V가 주어지며, i번째 줄에 주어지는 수는 X[i]와 V[i]이다. (1 ≤ X[i], V[i] ≤ N)

출력

첫째 줄에 문제의 조건을 만족하는 순열 P의 개수를 2000000011로 나눈 나머지를 출력한다.

제한

힌트

예제 1번의 경우 (3, 2, 1)이 가능하다.