数论板子

__int128 exgcd(__int128 as,__int128 bs,__int128 &x,__int128 &y){
    if(bs==0){
        x=1;
        y=0;
        return as;
    }
    __int128 ans=exgcd(bs,as%bs,y,x);
    y-=(as/bs)*x;
    return ans;
}

long long c(long long x,long long y){
    if(x>y) return 0;
    return jc[y]%mod*fc[x]%mod*fc[y-x]%mod;
}
long long a(long long x,long long y){
    if(x>y) return 0;
    return jc[y]%mod*fc[y-x]%mod;
}
long long lcs(long long x,long long y){
    if(x==0) return 1;
    return c(x%mod,y%mod)%mod*lcs(x/mod,y/mod)%mod;
}

__int128 excrt(){
    __int128 aa=a[1],bb=b[1],x,y;
    for(int i=2;i<=n;i++){
        __int128 an=exgcd(aa,a[i],x,y);
        if((b[i]-bb)%an) return -1;
        x=(b[i]-bb)/an*x%(a[i]/an);
        bb=aa*x+bb;
        aa=aa/an*a[i];
        bb%=aa;
    }
    return (bb%aa+aa)%aa;
}