首先推出 $ans=\frac{n!}{m!} \times \phi(m!)$

然后因为当 $a , b$ 互质时有 $\phi(ab)=\phi(a) \times \phi(b)$

所以 $ans=\frac{n!}{m!} \times \phi(p_{1})^{q_{1}} \times \phi(p_{2})^{q_{2}} \times \phi(p_{3})^{q_{3}} \times ... \times \phi(p_{k})^{q_{k}}$

（ $p_{i}$ 为 $m!$ 的质因子）

这时我们可以 $O(n)$ 地预处理出素数表和欧拉函数值表。

然后只要质因数分解就可以了。

我们知道，对于一个素数 $p$ ,在 $m!$ 中有 $\frac{m}{p} + \frac{m}{p^{2}} + \frac{m}{p^{3}} + ...+ \frac{m}{p^{k}}$ 个 $p$

（ $p^{k}\leq m$ ）

思路讲完了，代码如下：

$Code$

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define N 10000005
#define M 1000005
#define LL long long
using namespace std;
LL T,n,m,mod,cnt,ans;
LL pri[M],num[M],E[N];
bool book[N];
inline LL read() // 快读
{
	LL x=0;
	bool f=false;
	char ch=getchar();
	while(!isdigit(ch)) f|=(ch==45),ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
inline void Cout(LL x)
{
	if(!x) return ;
	Cout(x/10);
	putchar(x%10+48);
}
inline void out(LL x) // 快输
{
	if(x<0) x=-x,putchar(45);
	if(x) Cout(x);
	else putchar(48);
	putchar(10);
}
inline void Euler(int x) // 预处理素数表 (pri[]) 和欧拉函数值表 (E[])
{
    E[1]=1;
    for(int i=2;i<=x;i++)
	{
        if(!book[i])
		{
            pri[cnt++]=i;
            E[i]=i-1;
        }
        for(int j=0;j<cnt && pri[j]<=x/i;j++)
		{
            book[pri[j]*i]=true;
            if(i%pri[j]) E[i*pri[j]]=E[i]*(pri[j]-1);
            else
			{
                E[i*pri[j]]=E[i]*pri[j];
                break;
            }
        }
    }
}
inline LL QP(LL a,LL b) // 快速幂
{
    LL x=1,base=a;
    while(b)
    {
        if(b&1) x*=base;
        x%=mod;
        base*=base;
        base%=mod;
        b>>=1;
    }
    return x%mod;
}
int main()
{
	Euler(N-5);
	T=read();mod=read();
	while(T--)
	{
		memset(num,0,sizeof(num));
		n=read();m=read();
		ans=1;
		for(LL i=m;i<=n;i++) ans=(ans*i)%mod; // 求 n!/m!
		for(LL i=1;i<=cnt;i++)
		{
			if(pri[i]>m)
			{
				num[0]=i-1; // 不大于m的素数的个数
				break;
			}
			for(LL j=1;QP(pri[i],j)<=m;j++)
				num[i]+=m/QP(pri[i],j);
		}
		for(LL i=1;i<=num[0];i++)
			ans=(ans*QP(E[pri[i]],num[i]))%mod;
		out(ans);
	}
	return 0;
}

请各位 $dalao$ 不吝赐教

$Orz$