31504번 - 정렬된 프랙탈 수열

문제

$N$개의 양의 정수로 구성된 수열 $A$가 있다. 수열의 각 원소의 값은 $N$을 초과할 수 없으며, 비내림차순으로 정렬되어 있다. 또한 수열에는 값이 같은 원소가 2ドル$개 이상 있을 수 있다.

그리고 $A$에 의해 결정되는 길이 $N$의 수열 $B$를 다음과 같이 정의한다.

$$b_i = a_{a_{i}}$$

여기서 1ドル \le i \le N$인 모든 $i$에 대해, $a_i$는 $A$의 $i$번째 원소를, $b_i$는 $B$의 $i$번째 원소를 나타낸다.

이때, $A = B$가 되도록 하는 수열 $A$를 정렬된 프랙탈 수열이라고 하자.

문제를 어렵게 만들기 위해, 여기에 제약사항을 하나 추가해 보자. 수열 $A$에서 $K$개의 원소를 선택해 각각 지정한 값으로 고정하려고 한다. 고정된 값들은 이후 수정할 수 없다.

$N$과 제약사항에 대한 정보가 주어졌을 때, 길이가 $N$인 서로 다른 정렬된 프랙탈 수열의 개수를 $M$으로 나눈 나머지를 구해보자.

입력

첫 번째 줄에 세 정수 $N(1 \le N \le 10^{18}),ドル $M(1 \le M \le 10^9),ドル $K(0 \le K \le \min (N, 1,000円))$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $K$개의 줄에 걸쳐, 수열 $A$에서 지정된 값으로 고정할 원소의 위치 $i(1 \le i \le N)$와 지정할 값 ${v}_{i}(1 \le {v}_{i} \le N)$가 공백으로 구분되어 주어진다. $i$의 값은 중복되어 주어지지 않는다.

출력

서로 다른 정렬된 프랙탈 수열의 개수를 $M$으로 나눈 나머지를 출력한다.

제한

노트

수열 $X,ドル $Y$에 대하여 두 수열이 같기 위한 필요충분조건은 다음과 같다.

• $X$의 길이와 $Y$의 길이가 동일하다.
• 그 길이를 $N$이라 할 때, 1ドル \le i \le N$인 모든 $i$에 대하여 $X$의 $i$번째 원소를 $x_i,ドル $Y$의 $i$번째 원소를 $y_i$이라고 할 때, $x_i = y_i$이다.

만약 두 수열 $X,ドル $Y$가 같다면, 이를 $X = Y$로 표기한다.