lucas

题目传送门

裸题不解释。

代码：

#include<cstdio> #include<algorithm> using namespace std; const int p=10007; #define N p+5 int t,n,m,c[N],iv[N]; int C(int n,int m){ if (n<m) return 0; if (n<p&&m<p) return c[n]*iv[m]%p*iv[n-m]%p; return C(n/p,m/p)*C(n%p,m%p)%p; } int main(){ c[0]=c[1]=iv[0]=iv[1]=1; for (int i=2;i<=p;i++) c[i]=c[i-1]*i%p,iv[i]=p-p/i*iv[p%i]%p; for (int i=2;i<=p;i++) iv[i]=iv[i-1]*iv[i]%p; for (scanf("%d",&t);t;t--) scanf("%d%d",&n,&m),printf("%d\n",C(n,m)); return 0; }