传送门1
传送门2
写在前面：数论！数论！数论！
思路：
1.分析出题目本意就是求phi(m!)*n!/m!%r（这一步大概挺难想的，想出来这个后面就简单多了）
2.n!%r可以O(10^7)预处理
3.由phi(x)=x×(p1-1)/p1×(p2-1)/p2×……×(pi-1)/pi，其中p1,p2,p3……pi为x的质因数且各不相同我们可以得到phi(m!)/m!=(p1-1)/p1×(p2-1)/p2×……×(pi-1)/pi，而且由于是阶乘，那么m!的质因数一定小于等于m,即小于10^7，所以同样可以预处理1-10^7中的质数并求出形同上式的答案，对于除法运算采取求逆元操作,即求出每个质因数关于r的逆元即可
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define MAXN 10000000
using namespace std;
int t,r,n,m;
bool pd[10000001];
int phi[10000001],fac[10000001],prime[10000001];//这里的phi[i]并不是指i的φ，而是i!的φ
inline void exgcd(int a,int b,int &x,int &y)
{
if (b==0) {x=1;y=0;return;}
exgcd(b,a%b,x,y);
int x1=y,y1=x-a/b*y;
x=x1;y=y1;
}
inline int getinv(int p)
{
int x,y;
exgcd(p,r,x,y);
return (x%r+r)%r;
}
main()
{
scanf("%d%d",&t,&r);
fac[0]=1;
phi[1]=1;
for (int i=1;i<=MAXN;i++)
fac[i]=(LL)fac[i-1]*i%r;//加强制类型转换防止乘法爆int，下同
for (int i=2;i<=MAXN;i++)
if (!pd[i])
{
phi[i]=(LL)phi[i-1]*(i-1)%r*getinv(i)%r;
for (int j=2;i*j<=MAXN;j++)
pd[i*j]=1;//最朴素的筛法，可以用欧拉筛的说
}
else phi[i]=phi[i-1];
while (t--)
{
scanf("%d%d",&n,&m);
printf("%lld\n",(LL)fac[n]*phi[m]%r);
}
}