#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+5;

int T,R,cnt,p[MAXN],fac[MAXN],inv[MAXN],ans[MAXN];
bitset<MAXN> vis;

void init(){
    fac[0]=1;
    for(int i=1;i<MAXN;i++)
        fac[i]=1LL*fac[i-1]*i%R;
    
    for(int i=2;i<MAXN;i++){
        if(!vis[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&1LL*i*p[j]<MAXN;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }

    inv[1]=1;
    for(int i=2;i<MAXN&&i<R;i++)
        inv[i]=1LL*(R-R/i)*inv[R%i]%R;

    ans[0]=ans[1]=1;
    for(int i=2;i<MAXN;i++){
        ans[i]=ans[i-1];
        if(!vis[i]) ans[i]=1LL*ans[i]*(i-1)%R*inv[i]%R;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>T>>R;
    init();
    while(T--){
        int N,M;
        cin>>N>>M;
        cout<<1LL*fac[N]*ans[M]%R<<"\n";
    }
    return 0;
}