（上不了p站我要死了，侵权度娘背锅）
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的答案。
Sample Input
4
5 1
5 2
7 3
4 2
Sample Output
5
10
35
6
就是一道裸的组合数题，挂上自己的Lucas模板。
Lucas其实相当于将n、m按p进制分解求组合数，再乘起来。
当n < m时组合数的值为零，于是我们发现一个数按p进制分解后的C(a,b)中a有一半的几率小于b，而一旦出现这种情况答案就是0。所以在用Lucas定理时会有很大的概率答案为0。
当然这并不是Lucas定理有问题。仔细想想，如果我们把C(n,m)化为阶乘的形式，由于n和m都大于p（模数），所以阶乘的项里面很可能包含p或p的倍数。一旦出现p的倍数，答案就是0了。
模板
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#ifdef WIN32
#define RIN "%I64d"
#else
#define RIN "%lld"
#endif
#define ll long long
template <typename T>inline void read(T &res){
T k=1,x=0;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
res=k*x;
}
const ll mod=10007;
ll jiec[10010],niy[10010];
ll n,m;
void exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
return ;
}
ll x0,y0;
exgcd(b,a%b,x0,y0);
x=y0;
y=x0-(a/b)*y0;
}
ll inverse(ll a){
ll x,y;
exgcd(a,mod,x,y);
return (x%mod+mod)%mod;
}
void init(){
jiec[0]=niy[0]=1;
for(int i=1;i<mod;i++) jiec[i]=jiec[i-1]*i%mod;
niy[mod-1]=inverse(jiec[mod-1]);
for(int i=mod-2;i>=1;i--) niy[i]=niy[i+1]*(i+1)%mod;
}
ll comb(ll a,ll b){
return jiec[a]*niy[b]%mod*niy[a-b]%mod;
}
ll lucas(ll a,ll b){
if(a<b) return 0;
if(a==0&&b==0) return 1;
if(a<mod&&b<mod) return comb(a,b);
return lucas(a/mod,b/mod)*lucas(a%mod,b%mod)%mod;
}
void solve(){
read(n),read(m);
printf(RIN"
",lucas(n,m));
}
int main(){
init();
int t;
read(t);
while(t--) solve();
return 0;
}