一个数很大,并不能预处理,所以要进行公式变换,存前一个的值就好
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MD=,N=1e6+;
ll n,m,inv[N];
int main()
{
inv[]=inv[]=;
int T,ca=;
ios::sync_with_stdio(false),cin.tie(),cout.tie();
cin>>T;
for(int i=; i<N; ++i) inv[i]=(MD-MD/i)*inv[MD%i]%MD;
while(T--)
{
cin>>n>>m;
ll ans=m%MD,t=m%MD;
for(int i=;i<n&&i<m;i++)
{
t=t*(m%MD-i)%MD*(n%MD-i)%MD*inv[i]%MD;
ans=(ans+t)%MD;
}
cout<<"Case #"<<++ca<<": "<<ans<<"\n";
}
}