정렬된 프랙탈 수열

$N$개의 양의 정수로 이루어진 수열 $A$가 있다. $A$의 각 원소는 $N$을 넘지 않으며, $A$는 비내림차순으로 정렬되어 있다. 같은 값을 가진 원소가 둘 이상 있을 수 있다.

$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$개의 줄에는 위치 $i$ ($1 \le i \le N$)와 값 $v_i$ ($1 \le v_i \le N$)가 공백으로 구분되어 주어진다. 이는 $a_i$를 $v_i$로 고정한다는 뜻이다. 같은 위치가 두 번 이상 나오지 않는다.

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

두 수열 $X$와 $Y$가 같을 필요충분조건은 다음과 같다.

• $X$와 $Y$의 길이가 같다.
• 그 길이를 $N$이라 할 때, $1 \le i \le N$인 모든 $i$에 대해 $X$의 $i$번째 원소 $x_i$와 $Y$의 $i$번째 원소 $y_i$가 같다.

$X$와 $Y$가 같으면 $X = Y$로 표기한다.