题目链接：
    https://www.luogu.com.cn/problem/P4720

    与卢卡斯定理的区别：
    在求解 Exlucas（扩展卢卡斯定理） - 图1 的问题上，lucas方法中p必须为质数，Exlucas方法中p不一定是质数，也可以是合数。

    Exlucas作用：
    求解 p为非质数的 Exlucas（扩展卢卡斯定理） - 图2 问题
    方法中会使用快速幂，中国剩余定理等。

    ac代码：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. #define int long long
    4. const int N = 1e5+5;
    5. int a[N],b[N];
    6. int qmi(int a,int b,int p)
    7. {
    8.     int ans = 1;
    9.     while(b)
    10.     {
    11.         if(b&1)
    12.             ans = ans*a%p;
    13.         b >>= 1;
    14.         a = a*a%p;
    15.     }
    16.     return ans;
    17. }
    18. int exgcd(int a,int b,int &x,int &y)
    19. {
    20.     if(!b)
    21.     {
    22.         x=1,y=0;
    23.         return a;
    24.     }
    25.     int d = exgcd(b,a%b,y,x);
    26.     y -= a/b*x;
    27.     return d;
    28. }
    29. int inv(int a,int p)
    30. {
    31.     int x,y;
    32.     int d = exgcd(a,p,x,y);
    33.     return (x%p+p)%p;
    34. }
    35. int china(int n,int p)
    36. {
    37.     int ans = 0;
    38.     for (int i=1;i<=n;i++)
    39.     {
    40.         int mi = p/a[i];
    41.         int x = inv(mi,a[i]);
    42.         ans = (ans+b[i]*mi%p*x%p)%p;
    43.     }
    44.     return ans;
    45. }
    46. int g(int n,int p)
    47. {
    48.     if(n<p)
    49.         return 0;
    50.     return g(n/p,p)+n/p;
    51. }
    52. int f(int n,int p,int pk)
    53. {
    54.     if(!n)return 1;
    55.     int rou = 1;
    56.     int rem = 1;
    57.     for (int i=1;i<=pk;i++)
    58.         if(i%p)
    59.             rou = rou*i%pk;
    60.     rou = qmi(rou,n/pk,pk);
    61.     for (int i=pk*(n/pk);i<=n;i++)
    62.         if(i%p)
    63.             rem = rem*(i%pk)%pk;
    65.     return f(n/p,p,pk)*rou%pk*rem%pk;
    67. }
    68. int c_pk(int n,int m,int p,int pk)
    69. {
    70.     int fn = f(n,p,pk),fm = inv(f(m,p,pk),pk),fnm = inv(f(n-m,p,pk),pk);
    71.     int mi = qmi(p,g(n,p)-g(m,p)-g(n-m,p),pk);
    72.     return fn*fm%pk*fnm%pk*mi%pk;
    73. }
    74. int exlucas(int n,int m,int p)
    75. {
    76.     int tmp = p,cnt = 0;
    77.     for (int i=2;i<=tmp/i;i++)
    78.         if(tmp%i==0)
    79.         {
    80.             int pk = 1;
    81.             while(tmp%i==0)
    82.                 tmp/=i,pk*=i;
    83.             a[++cnt] = pk;
    84.             b[cnt] = c_pk(n,m,i,pk);
    85.         }
    86.     if(tmp>1)
    87.     {
    88.         a[++cnt] = tmp;
    89.         b[cnt] = c_pk(n,m,tmp,tmp);
    90.     }
    91.     return china(cnt,p);
    92. }
    93. signed main ()
    94. {
    95.     int n,m,p;
    96.     cin>>n>>m>>p;
    97.     cout<<exlucas(n,m,p);
    98.     return 0;
    99. }

    参考博客：
    https://blog.csdn.net/qq_39641976/article/details/110140597?ops_request_misc=&request_id=&biz_id=102&utm_term=%E6%89%A9%E5%B1%95%E5%8D%A2%E5%8D%A1%E6%96%AF%E5%AE%9A%E7%90%86%E5%92%8C%E5%8D%A2%E5%8D%A1%E6%96%AF%E5%AE%9A%E7%90%86%E7%9A%84%E5%8C%BA%E5%88%AB&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-110140597.first_rank_v2_pc_rank_v29&spm=1018.2226.3001.4187