这是一道模板题。

求 $\binom{n}{m}\bmod p$。

输入格式

一行三个整数 $n,m,p$。

显然你不想读入高精度数，因此我们用 $-1$ 来表示 $2^{64}$。当读入 $p=-1$ 时你应该认为 $p=2^{64}$。

输出格式

一行一个整数，表示答案。

输入输出样例

输入

5 3 114514

输出

10

说明/提示

本题共有 10 组数据，对于所有数据，$1\leq m\leq n\leq 10^{18},p=-1\cup p\geq 2$。

在前 $6$ 的数据点中，保证 $2\leq p\leq 10^6$ 。

在后 $4$ 个数据点中，保证输入 $p=-1$，即模数为 $2^{64}$。

前三组数据满足 $p\in prime$。

第四组数据满足 $\mu(p)\neq 0$，即 $p$ 为若干质数的乘积。

第五组数据满足 $p=2^{19}$。