要找[1,n!]中与m!互质的数的个数，而与m!互质必须满足不包含任意属于[1,m]的质数（因为m!是由[1,m]中所有质数乘来乘去组成的）

那么（这里反过来想，也可以认为是贡献法）对于属于[1,m]的质数p，[1,n!]中与p不互质的有n!/p个

那么对于一堆p，最后互质的就有 $n!-n!/p_{1}-n!/p_{2}......+容斥$ （因为 $p_{i} 、p_{j}$ 可能会重复，所以还要容斥一下）

这时发现上式与欧拉函数定义式相似，所以容斥方法也一样，-> $n!*(1-1/p_{1})*(1-1/p_{2}).....$

然后就好了，但是单独处理O(nT)，要优化一下，这里显然选择离线，可以对于n或m排个序，预处理n!或p[1]* p[2]* ...* p[m]，可以做到O(n+m/logm*logP) 复杂度O(n)

注意，当n>=P&&m>=P时，n!中 乘的P 会和 <=m的质数中 除的P 相互消掉，这时如果求逆元会使答案为0，而答案可能不为0 所以要特殊处理一下

详见此样例：

1 3
4 3

ans=2

#include<bits/stdc++.h>
using namespace std;
int mb,ct,prime[10000007];
bitset<10000007> not_prime;
void euler(){
	for(int i=2;i<=mb;i++){
		if(!not_prime[i]){
			prime[++ct]=i;
		}
		for(int j=1;j<=ct&&prime[j]*i<=mb;j++){
			not_prime[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}
int P;
struct node{
	int id,a,b;
}s[10004];
bool cmp(node x,node y){
	return x.b<y.b;
}
long long fpw(long long a,int b){
	long long ans=1;
	while(b){
		if(b&1) ans=ans*a%P;
		a=a*a%P;b>>=1;
	}return ans;
}
int T,as[10004],ma;
long long ans1=1,jc[10000007];
int main()
{
	scanf("%d%d",&T,&P);
	for(int i=1;i<=T;i++){
		scanf("%d%d",&s[i].a,&s[i].b);s[i].id=i;
		ma=max(ma,s[i].a);mb=max(s[i].b,mb);
	}
	sort(s+1,s+T+1,cmp);
	euler();
	jc[1]=1;
    for(int i=2;i<=min(ma,2*P);i++){//模P下，P需特殊处理，但2P不是质数不会影响，>=2P就是0了
		jc[i]=jc[i-1];
		if(i!=P) jc[i]=jc[i]*i%P;
	}
	for(int t=1,j=1;t<=T;t++){
		int n=s[t].a,m=s[t].b;
		while(j<=ct&&prime[j]<=m){
			ans1=ans1*(prime[j]-1)%P;
			if(prime[j]!=P){//特判P
				ans1=ans1*fpw(prime[j],P-2)%P;
			}j++;
		}
		if(n>=P&&m>=P||n<P&&m<P){//P会消掉||没有P
			as[s[t].id]=ans1*jc[n]%P;
		}
		else as[s[t].id]=0;//n或m中包含P
	}
	for(int i=1;i<=T;i++){
		printf("%d\n",as[i]);
	}
	return 0;
}