Description
LMZ有n个不同的基友，他每天晚上要选m个进行[河蟹]，而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢？当然，LMZ的一年有10007天，所以他想知道答案mod 10007的值。(1<=m<=n<=200,000,000)
Input
第一行一个整数t，表示有t组数据。(t<=200)
接下来t行每行两个整数n, m，如题意。
Output
T行，每行一个数，为C(n, m) mod 10007的答案。
思路：
不想说什么，标准的lucas，比luogu上的板子还简单
lucas大家应该都知道，不知道的可以看我的博客（抱歉啊，还有bug，没发布）
核心代码就一行：
(lucas(s/p,t/p)*zhs(s%p,t%p))%p
重点在预处理逆元
代码：
#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,p,t,ny[100005];
void qny()
{
ny[1]=1;
for(register int a=2;a<=p-1;a++)
{
ny[a]=(p-(p/a))*ny[p%a]%p;
}
}
int zhs(int q,int x)
{
if(q==0)
{
return 1;
}
long long ltt=1;
for(register int a=1;a<=q;a++)
{
ltt*=ny[a];
ltt%=p;
}
for(register int a=1;a<=q;a++)
{
ltt*=(x-a+1);
ltt%=p;
}
return ltt;
}
long long lucas(int s,int t)
{
if(t==0)
{
return 1;
}
else
{
return (lucas(s/p,t/p)*zhs(s%p,t%p))%p;
}
}
int main()
{
scanf("%d",&t);
p=10007;
qny();
for(int i=1;i<=t;i++)
{
scanf("%d%d",&n,&m);
printf("%lld\n",lucas(m,n));
}
}