卢卡斯定理求n大于modd时的C(n,m)

//fac[i]=i!,inv[i]=1/i!

long long fac[maxn],inv[maxn];
long long C(int x,int y)
{
	if(!y)	return 1;
	long long u = C(x / modd, y / modd),z;
	int v = x % modd, w = y % modd;
    if (v < w) z = 0;
    else z = (fac[v] * inv[w] % modd) * inv[v - w] % modd;
    return u * z % modd;
}

//预处理
fac[0]=1;
for(int i=1;i<=n;i++)	f[i]=(f[i-1]*i)%modd;
int kx=min((int)modd-1,n);
inv[kx]=Pow(fac[kx],modd-2);
for(int i=kx-1;i>=0;i--)	inv[i]=inv[i+1]*(i+1)%modd;

模版：https://www.luogu.com.cn/problem/P3807