시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 5 2 33.333%

문제

크기가 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 ≤ 109, 0 ≤ M ≤ 104)가 주어진다. 둘째 줄부터 M개의 줄에는 배열 X와 V가 주어지며, i번째 줄에 주어지는 수는 X[i]와 V[i]이다. (1 ≤ X[i], V[i] ≤ N)

출력

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

예제 입력 1

2
3 0
3 2
3 1
1 2

예제 출력 1

1
0

힌트

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

출처