DivModulo

Modulo (mod) is a very common operator on integers. For two integers $n$ and $d$ with $d > 0$, $r \equiv (n \bmod d)$ is defined as the value $r$ such that $0 \le r < d$ and there exists an integer $q$ with $n = q \times d + r$. For example, $(200 \bmod 5) \equiv 0$ means the remainder of 200 divided by 5 is 0.

Here is another new operator called DivModulo (dmod) defined as follows. For two integers $n$ and $d$ with $d > 0$, $r \equiv (n \mathbin{\mathrm{dmod}} d)$ is defined as the value $r$ such that $r \equiv (m \bmod d)$ where there exist integers $m$ and $h$ with $n = m \times d^h$ and $d$ is not a factor of $m$. For example, $(200 \mathbin{\mathrm{dmod}} 5) \equiv 3$, since $200 = 8 \times 5^2$ and $(8 \bmod 5) \equiv 3$.

Consider the factorials and the combination function. For an integer $M \ge 0$, the factorial $M!$ is defined as $M! = M \times (M-1) \times (M-2) \times \cdots \times 3 \times 2 \times 1$, and $0! = 1$ is defined. For integers $M$ and $N$ with $0 \le N \le M$, the combination function $C(M, N)$ is defined as $C(M, N) = M!/(N! \times (M-N)!)$. Now given three integers $M$, $N$, $D$ with $D > 0$, compute $C(M, N) \mathbin{\mathrm{dmod}} D$. For example, $(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$.

Three integers $M$, $N$, and $D$ are given in one line.

Print $C(M, N) \mathbin{\mathrm{dmod}} D$ in one line.

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