- M-N の差が小さいことを利用して計算する。
- p^2 == M のときの罠にはまって WA した。コーナーケースの処理が甘い...。
class NFactorialModM {
public:
void solve(void) {
int T;
cin>>T;
REP(t,T)
{
int N,M;
cin>>N>>M;
if (N >= M || M == 1)
{
cout<<0<<endl;
continue;
}
ll p;
for (p = 2; p*p <= M; ++p)
{
if (M%p==0)
break;
}
if (p*p > M)
{
ll a = 1;
for (int i = 1; i < M-N; ++i)
(a *= (N+i)) %= M;
cout<<(mod_inverse(a,M)*(M-1))%M<<endl;
continue;
}
if (M/p <= N && M != p*p)
{
cout<<0<<endl;
continue;
}
if (p*p == M && 2*p <= N)
{
cout<<0<<endl;
continue;
}
ll a = 1;
for (int i = 1; i <= N; ++i)
(a *= i) %= M;
cout<<a<<endl;
}
}
};