DivModulo

Modulo(mod)는 정수에서 매우 흔히 쓰이는 연산이다. 두 정수 $n$과 $d > 0$에 대해 $r \equiv (n \bmod d)$는 $0 \le r < d$이고 $n = q \times d + r$인 정수 $q$가 존재하는 $r$로 정의된다. 예를 들어 $(200 \bmod 5) \equiv 0$은 200을 5로 나눈 나머지가 0임을 뜻한다.

다음은 DivModulo(dmod)라는 새로운 연산의 정의이다. 두 정수 $n$과 $d > 0$에 대해 $r \equiv (n \mathbin{\mathrm{dmod}} d)$는 $r \equiv (m \bmod d)$이고 $n = m \times d^h$이며 $d$가 $m$의 약수가 아닌 정수 $m$과 $h$가 존재하는 $r$로 정의된다. 예를 들어 $(200 \mathbin{\mathrm{dmod}} 5) \equiv 3$이다. $200 = 8 \times 5^2$이고 $(8 \bmod 5) \equiv 3$이기 때문이다.

팩토리얼과 조합 함수를 생각하자. 정수 $M \ge 0$에 대해 팩토리얼 $M!$은 $M! = M \times (M-1) \times (M-2) \times \cdots \times 3 \times 2 \times 1$로 정의되고 $0! = 1$로 정의된다. $0 \le N \le M$인 정수 $M$과 $N$에 대해 조합 함수 $C(M, N)$은 $C(M, N) = M!/(N! \times (M-N)!)$로 정의된다. 세 정수 $M$, $N$, $D$가 $D > 0$을 만족하며 주어질 때 $C(M, N) \mathbin{\mathrm{dmod}} D$를 계산하시오. 예를 들어 $(C(9, 2) \mathbin{\mathrm{dmod}} 3) \equiv (36 \mathbin{\mathrm{dmod}} 3) \equiv (4 \times 3^2 \mathbin{\mathrm{dmod}} 3) \equiv (4 \bmod 3) \equiv 1$이다.

한 줄에 세 정수 $M$, $N$, $D$가 주어진다.

$C(M, N) \mathbin{\mathrm{dmod}} D$를 한 줄에 출력한다.

• $1 \le M \le 4 \times 10^{18}$
• $0 \le N \le M$
• $2 \le D \le 1.6 \times 10^7$