本题解讲的是快速暴力组合数的方法，需要知道以下知识(能做此题的大佬应该都知道吧。。。)：

欧拉筛，组合数公式,卡速米(这个应该没人会吧？) 否则将引起不适

设π(x->y)为从x连乘到y(数学公式编译器崩了。。。)

组合数，大家都知道，公式为C(n,m)=!n/(!m*!(n-m)) 我们将它化简一下:π(m+1->n)/!(n-m)(当然,如果n-m>m,我们可以将m替换为n-m进行优化)

然后，我们手算是将所有数列举出来再一一 **约分** ，

我们知道，约分就是约掉分子分母的公因数，

那么如果我们将分子分母的数全部转换成几个质数相乘的形式，然后统计每个质数的个数，再加个快速幂，不就可以高效的解出来了吗？

那么，我们该如何分解质因数呢？

答案是：欧拉筛求最小质因数！！

我们可以用欧拉筛求出x的最小质因数，然后用个while，直到x==1时结束，以下为代码： 

#include<bits/stdc++.h>//笔者懒,用的万能头文件~
using namespace std;
const int N=1e5+1;//范围
int f[N],zhi[N>>1],hav[N],e;//质数表其实不用开那么大,反正少一半是没毛病的(除偶数)
inline void oula(int maxe){
    for(int i=2;i<=maxe;++i){
        if(!f[i]){//如果没被筛过(质数)
            f[i]=i;//质数的最小质因数是它本身
            zhi[++e]=i;//质数表
        }
        for(int j=1;j<=e;++j){
            if(i*zhi[j]>maxe){//如果超出范围
               break;//退出
            }
            f[i*zhi[j]]=zhi[j];//标记最小质因数为zhi[j],注意千万不要写i,虽然i也是i*zhi[j]的因数,但i不一定是质数！！
            if(i%zhi[j]==0){//欧拉筛速度快的关键。。。
                break;
            }
        }
    }
}
inline int ksc(int x,int y,int p){//快速乘
    int ans=0;
    while(y){
        if(y&1){
            ans+=x;
            ans%=p;
        }
        x+=x;
        x%=p;
        y>>=1;
    }
    return ans%p;
}
inline int ksm(int x,int y,int p){//快速幂
    int ans=1;
    while(y){
        if(y&1){
            ans=ksc(ans,x,p);
        }
        x=ksc(x,x,p);
        y>>=1;
    }
    return ans%p;//这里记得模p,不然有的时候可能会错
}
inline void up(int x){//分解做分子
    while(x>1){
        hav[f[x]]++;
        x/=f[x];
    }
}
inline void down(int x){//分解做分母
    while(x>1){
        hav[f[x]]--;
        x/=f[x];
    } 
}
inline int C(int n,int m,int p){
    if(n<m){//特判一下
        return 0;
    }
    if(n-m>m){
        m=n-m;//小优化
    }
    for(int i=m+1;i<=n;++i){
        up(i);//将i质因数分解作为分子
    }
    for(int i=2;i<=n-m;++i){
        down(i);//将i质因数分解作为分母
    }
    int ans=1;
    for(int i=1;i<=e;++i){//枚举每一个质数
        if(hav[zhi[i]]){//如果结果中出现了第i个质数
            ans=ksc(ans,ksm(zhi[i],hav[zhi[i]],p),p);
            hav[zhi[i]]=0;//记得清空
        }
    }
    return ans;
}
int main(){
    oula(N-1);//欧拉筛求最小质因数,由于之前加了1所以这里要减1
    int n,m,p;
    scanf("%d%d%d",&n,&m,&p);//输入
    printf("%d",C(n,m,p));
    return 0;
}

至于本题，只需要将这个快速暴力组合数的方法代个卢卡斯定理就行了~(虽然直接算甚至还快些,不过如果n和m再大点就必须用卢卡斯了,亲测直接暴力+o2 98ms 不加o2 123ms)