#include<cstdio>

 #include<iostream>

 #define ll long long

 #define N 10000009

 using namespace std;

 int jie[N],ine[N],sum[N];

 int T,R,n,m,tot,zhan[N];

 bool mark[N];

 void exgcd(int a1,int a2,int &x,int &y)

 {

     if(!a2)

       {

         x=;

         y=;

         return;

       }

     exgcd(a2,a1%a2,x,y);

     int t=x;

     x=y;

     y=t-a1/a2*y;

 }

 int main()

 {

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

     jie[]=;

     for(int i=;i<=N-;i++)

       jie[i]=(ll)jie[i-]*i%R;

     for(int i=;i<=N-;i++)

       {

         if(!mark[i])

           {

             int y;

             exgcd(i,R,ine[i],y);

             ine[i]=(ine[i]+R)%R;

             zhan[++tot]=i;

           }

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

               {

                 mark[zhan[j]*i]=;

                 if(i%zhan[j]==)

                   break;

               }

     }

     sum[]=;

     for(int i=;i<=N-;i++)

       {

         sum[i]=sum[i-];

         if(!mark[i])

           sum[i]=(ll)sum[i]*(i-)%R*ine[i]%R;

       }

     for(;T;T--)

       {

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

         printf("%d\n",(ll)jie[n]*sum[m]%R);

       }

     return ;

 }