该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

【题意】20230912scy重制数据
给定整数 $n, m, p$ 的值，求出 $C_n ^m \bmod p$ 的值。
注: $C$ 表示组合数。
lucas（卢卡斯定理）：Lucas(n,m)=C(n%P,m%P)*Lucas(n/P,m/P)%P;
作用：求n和m很大组合数，前提是P比较小。

【输入格式】
第一行是一个正整数 T，表示数据组数；
接下来是 T组数据，每组数据有 3 个正整数 n,m,p （$1 \le m \le n \le 10^{18}，p<10^6$，保证p 是素数，如果p不是素数又是另外一个故事）。

【输出格式】
对于每组数据，输出一个正整数，表示结果。

【输入样例】
2
5 2 3
5 2 61

【输出样例】
1
10

Hint

G27 求组合数 卢卡斯定理

#include<bits/stdc++.h> 
using namespace std; 
typedef long long LL; 
const int N=1e6+10;
LL P,fac[N]; 
LL qpow(LL a,LL b)  
{
	LL res=1%P;a%=P;
	for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}  
LL C(LL n,LL m)  
{
	return (n<m) ? 0ll :fac[n]*qpow(fac[m],P-2)%P*qpow(fac[n-m],P-2)%P;  
}  
LL Lucas(LL n,LL m)  
{
	return (m==0) ? 1ll : C(n%P,m%P)*Lucas(n/P,m/P)%P;  
}  
int main()  
{
	int T;cin>>T;
	while(T--)
	{
		LL n,m;cin>>n>>m>>P;
		fac[0]=1;for(int i=1;i<=P;i++)fac[i]=fac[i-1]*i%P; 
		cout<<Lucas(n,m)<<"\n";
	}
	return 0;  
}