给定n组询问，每组询问给定三个整数a,b,p，其中p是质数，请你输出Cba mod p的值。

输入格式
第一行包含整数n。

接下来n行，每行包含一组a,b,p。

输出格式
共n行，每行输出一个询问的解。

数据范围
1≤n≤20,
1≤b≤a≤1018,
1≤p≤105,

输入样例：

3
5 3 7
3 1 5
6 4 13

输出样例：

3
3
2

卢卡斯定理证明


本题代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qsm(ll a,ll k,ll p)
{
    ll res=1;
    while(k)
    {
        if(k&1)res=res*a%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
ll c(ll a,ll b,ll p)
{
    if(b>a)return 0;                        //如果有一项的b>a则说明在(1+x)^中x^b的系数为0;
    ll res=1;
    for(ll i=1,j=a;i<=b;i++,j--)            //Cab=(a-b+1)!/b!;
    {
        res=res*j%p;
        res=res*qsm(i,p-2,p)%p;             //快速幂求逆元;
    }
    return res;
}
ll lucas(ll a,ll b,ll p)
{
    if(a<p&&b<p)return c(a,b,p);
    return c(a%p,b%p,p)*lucas(a/p,b/p,p)%p;//递归求解的过程;
}
int main()
{
    ll k;
    cin>>k;
    while(k--)
    {
        ll a,b,p;
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }
    return 0;
}