取模（mod）是整数中非常常见的运算符。对于两个整数 $n$ 和 $d$（$d > 0$），$r \equiv (n \bmod d)$ 定义为 $0 \le r < d$ 且存在整数 $q$，使得 $n = q \times d + r$。例如，$(200 \bmod 5) \equiv 0$ 表示 200 除以 5 的余数为 0。这里定义了另一个新的运算符，称为 DivModulo（dmod），定义如下：对于两个整数 $n$ 和 $d$（$d > 0$），$r \equiv (n \text{ dmod } d)$ 定义为存在两个整数 $m$ 和 $h$，使得 $r \equiv (m \bmod d)$，$n = m \times d^h$，且 $d$ 不能整除 $m$。例如，$(200 \text{ dmod } 5) \equiv 3$，因为 $(200 \text{ dmod } 5) \equiv (8 \times 5^2 \text{ dmod } 5) \equiv (8 \bmod 5) \equiv 3$。

考虑阶乘和组合函数。对于整数 $M \ge 0$，阶乘 $M!$ 定义为 $M! = M \times (M - 1) \times (M - 2) \times \dots \times 3 \times 2 \times 1$，并定义 $0! = 1$。对于整数 $M$ 和 $N$（$0 \le N \le M$），组合函数 $C(M, N)$ 定义为 $C(M, N) = \frac{M!}{N! \times (M - N)!}$。

现在给定三个整数 $M, N, D$（$D > 0$），请计算 $C(M, N) \text{ dmod } D$。例如，$(C(9, 2) \text{ dmod } 3) \equiv (36 \text{ dmod } 3) \equiv (4 \times 3^2 \text{ dmod } 3) \equiv (4 \bmod 3) \equiv 1$。

输入格式

一行包含三个整数 $M, N$ 和 $D$。

输出格式

输出 $C(M, N) \text{ dmod } D$ 的结果。

数据范围

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

样例

样例输入 1

9 2 3

样例输出 1

1

样例输入 2

5 2 5

样例输出 2

2

样例输入 3

6 3 6

样例输出 3

2

样例输入 4

7654321 1234567 1050

样例输出 4

210