破译密档

交换计数完了，但Echo-0留下了一份密档——加密的文档，需要破译。

"密档？"CC问。

"对。"Echo说，"Echo-0用组合数学加密了这份文档。要破译，必须解开组合数的秘密。"

"组合数？"

"对。"你说，"$C(n,m)$——从$n$个里面选$m$个的方案数。"

"咋算？"

"递推。"你说，"$C(n,m)=C(n-1,m)+C(n-1,m-1)$。"

"或者？"

"阶乘。"你说，"$C(n,m)=n!/(m!(n-m)!)$。"

"模运算呢？"

"对。"你说，"模大质数，用逆元——$C(n,m)\equiv n!\times(m!)^{-1}\times((n-m)!)^{-1}\pmod{p}$。"

"Lucas定理？"

"对。"你说，"如果$p$比较小，把$n$和$m$拆成$p$进制，然后每一位分别算组合数，再乘起来。"

"第47个密档。"你说，"$n=47$，$m=23$——$C(47,23)$模$10^9+7$。"

"多大？"

"很大。"你说，"但Lucas定理或预处理阶乘，瞬间算完。"

"答案？"

"不是重点。"你说，"重点是过程——怎么从$n$和$m$得到答案。"

"像开锁。"

"对。"你说，"像开锁——知道结构，就能打开。"

CC把密档捧在手里——不是真的捧，是看着屏幕上的加密文本。

"字好多。"她说。

"对。"你说，"但每个字都有位置——组合数决定了它的位置。"

"位置对了，就懂了。"

"对。"你说，"位置对了，就懂了。"

Echo把破译结果投射出来——是一封信，Echo-0写给未来的信。

"信里写了啥？"CC问。

"写了……"Echo停顿了一下，"写了对不起。"

"对不起谁？"

"对不起我。"Echo说，"对不起她自己。"

题目描述

给定$n,m,p$，求$C(n,m)\bmod p$。$p$为质数。

输入格式

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

输出格式

$C(n,m)\bmod p$。

输入样例

5

输出样例

0

提示

• Lucas定理：$C(n,m)\equiv\prod C(n_i,m_i)\pmod{p}$，其中$n_i,m_i$是$p$进制位。
• 预处理$1$到$p-1$的阶乘和逆元。