#include<bits/stdc++.h>
#define int long long
#define r p
const int N=1e7;
int t,r;
using namespace std;
int inv[N+10];
int jc[N+10];
int prime[N+10];
bool isprime[N+10];
int sum[N+10];//在m的阶乘中所有质因子 的(pi-1)/pi积
int sumnow=1;//当前结果
int cnt=0;
void init() {
inv[1]=1;
jc[0]=1;
for(int i=1; i<=N; i++) {
jc[i]=jc[i-1]*i;
jc[i]%=p;
}
for(int i=2; i<=N; i++) {
inv[i]=((p-(p/i)*inv[p%i]%p))%p;
}
for(int i=2; i<=N; i++) {
if(isprime[i]==0) { //找到质数
prime[++cnt]=i;
sumnow*=(i-1)*inv[i]%p;
sumnow%=p;
}
for(int j=1; prime[j]*i<=N; j++) {
isprime[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
sum[i]=sumnow;
}
}
signed main() {
cin>>t>>r;
init();
for(int i=1; i<=t; i++) {
int n,m;
scanf("%d%d",&n,&m);
int ans=(jc[n]*sum[m])%p;
printf("%lld\n",ans%p);
}
return 0;
}
677ms/244.69MB WA
#2 Wrong Answer.wrong answer On line 1 column 1, read 0, expected 2. 679ms/244.57MB WA
#3 Wrong Answer.wrong answer On line 10 column 1, read 0, expected 5. 677ms/244.58MB WA
#4 Wrong Answer.wrong answer On line 125 column 1, read 0, expected 2. 676ms/244.59MB WA
#5 Wrong Answer.wrong answer On line 177 column 1, read 0, expected 3. 758ms/244.68MB AC
#6 Accepted, 得分 10.ok accepted 780ms/244.68MB AC
#7 Accepted, 得分 10.ok accepted 684ms/244.60MB AC
#8 Accepted, 得分 10.ok accepted 680ms/244.70MB AC
#9 Accepted, 得分 10.ok accepted 773ms/244.70MB WA
#10 Wrong Answer.wrong answer On line 1 column 1, read 0, expected 7. 694ms/244.58MB WA
#11 Wrong Answer.wrong answer On line 3 column 1, read 0, expected 4.
Subtask #1 675ms/244.59MB WA #1 Wrong Answer.wrong answer On line 1 column 1, read 0, expected 2.