考虑到 $\gcd(a,m!)=1\to \gcd(a+m!, m!)=1\to \gcd(a+k\cdot m!,m!)=1,k\in \mathbf Z_+$ 。

因此 $(0,m!]$ 中与 $m!$ 互质的个数，与 $(m!,2m!],(2m!,3m!],\cdots, (n!-m!,n!]$ 中的均相同。

而 $(0,m!]$ 中与 $m!$ 互质的数的个数为 $\displaystyle \boldsymbol \varphi(m!)=m!\prod_{p\in Prime}^m{p-1\over p}$ 。

故答案为 $\displaystyle {n!\over m!}\cdot \boldsymbol \varphi(m!)=n!\prod_{p\in Prime}^m{p-1\over p}$ 。

考虑线筛时分别用 $frac_n, cntf_n$ 维护 $n!$ 中的不含 $R$ 因子的所有数乘积，与 $R$ 因子的出现次数。

再分别用 $infr_n, cnti_n$ 维护 $\displaystyle \prod_{p\in prime}^n {p-1\over p}$ 中不含 $R$ 因子的所有数乘积，与 $R$ 因子的出现次数。

询问 $n, m$ 时，若 $cntf_n+cnti_m>0$ ，说明答案含有 $R$ 因子，取模后为 $0$ ；否则 $cntf_n+cnti_m=0$ ，答案不含有 $R$ 因子，则取模后为 $frac_n\cdot infr_m\bmod R$ 。

参考代码（略丑）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef double db;
#define fi first
#define se second
const int Lim=1e7, MAXN=Lim+10;
int R;
int prime[MAXN/10], cntprime, fc[MAXN], frac[MAXN], cntf[MAXN], infr[MAXN], cnti[MAXN];
inline int fpow(int a, int x) { int ans=1; for(;x;x>>=1,a=(ll)a*a%R) if(x&1) ans=(ll)ans*a%R; return ans; }
inline void init() {
    frac[0]=frac[1]=infr[0]=infr[1]=1;
    for(int i=2,val; i<=Lim; ++i) {
        frac[i]=frac[i-1];
        cntf[i]=cntf[i-1];
        infr[i]=infr[i-1];
        cnti[i]=cnti[i-1];
        if(!fc[i]) {
            fc[i]=prime[++cntprime]=i;
            if(i==R) {
                infr[i]=(ll)infr[i]*(i-1)%R;
                --cnti[i];
            }
            else {
                val=i-1;
                while(val%R==0)
                    ++cnti[i], val/=R;
                infr[i]=(ll)infr[i]*val%R*fpow(i, R-2)%R;
            }
        }
        val=i;
        while(val%R==0)
            ++cntf[i], val/=R;
        frac[i]=(ll)frac[i]*val%R;

        for(int j=1; j<=cntprime; ++j)
            if(prime[j]*i>Lim||prime[j]>fc[i]) break;
            else fc[prime[j]*i]=prime[j];
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin>>T>>R;
    init();
    int n, m;
    while(T--&&cin>>n>>m) {
        int res=(ll)frac[n]*infr[m]%R;
        int cnt=cntf[n]+cnti[m];
        if(cnt>0) res=0;
        cout<<res<<"\n";
    }
    cout.flush();
    return 0;
}