学步园

一个主要问题就是364875103=97*3761599;

#include <cstdio>
#include <iostream>
#include <cstdlib>
#define M (364875103LL)
#define M1 (97LL)
#define M2 (M/M1)
#define LL long long
using namespace std;
LL fac1[M1+9],fac2[M2+9];
LL mod(LL a,LL b,LL m)
{
    a%=m;
    LL ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%m;
        a=a*a%m;
        b>>=1;
    }
    return ans;
}

LL inv(LL a,LL m)
{
    return mod(a,m-2,m);
}

LL C(int n,int m,LL mod,LL *fac)
{
    if(n<m) return 0;
    return fac[n]*inv(fac[n-m]*fac[m],mod)%mod;
}

LL lucas(int n,int m,LL mod,LL *fac)
{
    if(m==0) return 1;
    return C(n%mod,m%mod,mod,fac)*lucas(n/mod,m/mod,mod,fac);
}

int main()
{
    int T,cas=1;
    int a[20];
    fac1[0]=fac2[0]=1;
    for(LL i=1;i<M1;i++) fac1[i]=fac1[i-1]*i%M1;
    for(LL i=1;i<M2;i++) fac2[i]=fac2[i-1]*i%M2;
    LL inv1=inv(M1,M2)*M1,inv2=inv(M2,M1)*M2;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,k;
        scanf("%d %d",&n,&m);
        int now,pre=0;
        LL a1,a2,ans=1;
        scanf("%d",&k);
        for(int i=0;i<k;i++) scanf("%d",&a[i]);
        a[k]=m;
        for(int i=0;i<k;i++)
        {
            a1=lucas(n+a[i+1]-a[i]-1,a[i+1]-a[i],M1,fac1);
            a2=lucas(n+a[i+1]-a[i]-1,a[i+1]-a[i],M2,fac2);
            LL aa=(a1*inv2+a2*inv1)%M;
            ans=ans*(aa)%M;
        }
        printf("Case #%d: %I64d\n",cas++,ans);
    }
    return 0;
}