Lucas

/*
Lucas定理 C(n,m)%p(p为素数)
C(n,m)与C(a[n],b[n])*C(a[n-1],b[n-1])*C(a[n-2],b[-2])*....*C(a[0],b[0])模p同余
a,b 是n，m在p进制下的数
有的推公式： (C(n%p,m%p,p)*Lcs(n/p,m/p,p))%p;
关键是求 C(n%p,m%p,p) 递归会很慢 for的话会爆掉
这里用一个定理：a/b%p <--> a*x%p  x为b在b%p下的逆元
再来一个定理：x=b^(p-2)   x为b在%p下的逆元  p为素数
然后预处理一下阶乘就ok了 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[1100];
void get_f(int p)
{
    f[0]=1;
    for(int i=1;i<=p;i++)
      f[i]=f[i-1]*i%p;
}
int Mi(int a,int m,int p)
{
    if(m==0)return 1;
    int x=Mi(a,m/2,p);
    x=x*x%p;
    if(m%2==1)x=x*a%p;
    return x;
}
int C(int n,int m,int p)
{
    if(m>n)return 0;
    return  f[n]*Mi(f[m]*f[n-m],p-2,p)%p;
}
int Lcs(int n,int m,int p)
{
    if(m==0)return 1;
    return (C(n%p,m%p,p)*Lcs(n/p,m/p,p))%p;
}
int main()
{
    int n,m,p;
    scanf("%d%d%d",&n,&m,&p);
    get_f(p);
    printf("%d
",Lcs(n,m,p));
    return 0;
}