题意：

给出n,m，还有k个质数$p_1,…,p_k$，有$M=p1·p2···p3$，求$C_n^m\%M$的值。其中$T≤20,1≤m≤n≤10^{18},1≤k≤10,M≤10^{18},pi≤10^5$。

思路：

这题目有点套路啊？（模板一顿乱套系列…然而比赛的时候并没有想到…完全忘记了之前学的中国剩余定理啊…

用Lucas定理处理出每个$C_n^m\%p_i$的值，可以得到一堆模质数后的值，这时候就用中国剩余定理。

Lucas定理：

适用于$n<=10^{18},m<=10^{18},p<=10^5$且p为素数的情况。

复杂度为$O(log_p(n)*p)$，在这个数据范围下大概是是$10^7$的大小，所以是可以跑的。

中国剩余定理：

具体见这篇：http://pattle.xyz/2018/01/25/51nod-1079-中国剩余定理/

一个正整数K，给出K Mod 一些质数的结果，求符合条件的最小的K。

举个栗子，K%3=2，K%5=3，K%7=2。

a=2×5×7×inv(5×7,3)

b=3×3×7×inv(3×7,5)

c=2×3×5×inv(3×5,7)

答案就是a+b+c。

中国剩余定理这里有个地方会爆ll（见注释），所以要用到快速乘…之前没用到过，存个模板吧。

快速乘：

什么时候才用得到快速乘法呢，当两个数相乘可能超过ll范围的时候用。

ll PowerMulti(ll m,ll n,ll mod)
{
    ll ans=0;
    while(n)
    {
        if(n&1)
            ans+=m;
        m=(m+m)%mod;
        ans%=mod;
        ans%=mod;
        n>>=1;
    }
    return ans;
}

代码：

typedef long long ll;
ll p[110],m[110];
void extgcd(ll a,ll b,ll d,ll &x,ll &y)   //a,b都为正整数
{
    if(b==0){d=a;x=1;y=0;}
    else{extgcd(b,a%b,d,y,x);y=y-x*(a/b);}
}
ll inverse(ll a,ll p)
{
    ll d,x,y;
    extgcd(a,p,d,x,y);
    return (x%p+p)%p;
}
ll PowerMulti(ll m,ll n,ll mod)
{
    ll ans=0;
    while(n)
    {
        if(n&1)
            ans+=m;
        m=(m+m)%mod;
        ans%=mod;
        ans%=mod;
        n>>=1;
    }
    return ans;
}
long long PowerMod(long long a,long long b,long long c)
{
    long long ans=1;
    long long k;
    k=a;
    k=k%c;
    while(b>0)
    {
        if(b&1)
            ans=(ans*k)%c;
        b>>=1;
        k=(k*k)%c;
    }
    return ans;
}
long long C(long long n,long long m,long long p)
{
    if(m>n)return 0;
    long long ans = 1;
    for(int i=1;i<=m;i++)
    {
        long long a=(n+i-m)%p;
        long long b=i%p;
        ans=ans*(a*PowerMod(b,p-2,p)%p)%p;
    }
    return ans;
}
long long Lucas(long long n,long long m,long long p)
{
    if(m==0)return 1;
    return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll x,y;
        int n;
        ll mul=1;
        scanf("%lld%lld%d",&x,&y,&n);
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&p[i]);
            m[i]=Lucas(x,y,p[i]);
            mul*=p[i];
        }
        //for(int i=0;i<n;i++)
            //printf("%lld\n",m[i]);
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            ll temp=mul/p[i];
            ll tp=(inverse(temp,p[i]))%mul;
            temp=(temp*m[i])%mul;
            ans=(ans+PowerMulti(temp,tp,mul))%mul;//可能会爆ll，所以用快速乘
            //ans=(ans+(temp*tp)%mul)%mul;
        }
        printf("%lld\n",ans);
    }
    return 0;
}