n>=m,所以就变成了求

而

p为m!的素因子,即为m内的所有素数,问题就转化为了求

只需要预处理出素数，阶乘，逆元即可

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#define N 10000001

using namespace std;

bool bo[N+100];

long long prime[700000],fc[N+100],ans[N+100],ny[N+100];

int tot,T,n,m,p;

void init(){

    fc[1]=1;

    for(int i=2;i<=N;i++)fc[i]=(fc[i-1]*i)%p;

    for(int i=2;i<=N;i++){

        if(!bo[i])prime[++tot]=i;

        for(int j=1;j<=tot&&i*prime[j]<=N;j++){

            bo[i*prime[j]]=1;

            if(!i%prime[j])break;

        }

    }

    ny[1]=1;

    for(int i=2;i<=N&&i<p;i++)ny[i]=(p-p/i)*ny[p%i]%p;

    ans[1]=1;

    for(int i=2;i<=N;i++){

        if(!bo[i])ans[i]=ans[i-1]*(i-1)%p*ny[i%p]%p;

        else ans[i]=ans[i-1];

    }

}

int main(){

    scanf("%d%d",&T,&p);

    init();//printf("tot==%d\n",tot);

    while(T--){

        scanf("%d%d",&n,&m);

        printf("%d\n",(fc[n]*ans[m])%p);

    }

    return 0;

}