难度： 蓝

算法： 数学，Lucas 定理。

发现题目是让我们求 $(_m^n)$ 的值。

直接套 Lucas 定理的板子。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll q,a,b,p=10007;
ll qp(ll x,ll y){
	ll as=1,bs=x;
	while(y){
		if(y%2) as=as*bs%p;
		bs=bs*bs%p;
		y/=2;
	}
	return as;
}
ll inv(ll x){
	return qp(x,p-2);
}
ll c(ll x,ll y){
	if(x<y) return 0;
	if(y>x-y) y=x-y;
	ll r1=1,r2=1;
	for(ll i=0;i<y;i++){
		r1=(r1*(x-i))%p;
		r2=(r2*(i+1))%p;
	}
	return r1*inv(r2)%p;
}
ll luc(ll x,ll y){
	if(y==0) return 1;
	return luc(x/p,y/p)*c(x%p,y%p)%p;
}
int main(){
	scanf("%lld",&q);
	while(q--){
		scanf("%lld%lld",&a,&b);
		printf("%lld\n",luc(a,b));
	}
}