#include<bits/stdc++.h> using namespace std; #define int long long const int MAXN=120,N=50,Mod=1000000007; int _,n,m,a,p,q,f[MAXN][MAXN],qi; int Pow(int x,int y){int rt=1;while(y){if(y&1)rt=rt*x%p;y>>=1;x=x*x%p;}return rt;} struct viar{ int x,y,a[MAXN][MAXN]; viar operator *(const viar&G)const{ viar rt;rt.x=x;rt.y=G.y; for(int i=1;i<=rt.x;i++){ for(int j=1;j<=rt.y;j++)rt.a[i][j]=0; } for(int i=1;i<=x;i++){ for(int k=1;k<=y;k++){ int r=a[i][k]; for(int j=1;j<=G.y;j++){ rt.a[i][j]+=(r*G.a[k][j])%p; rt.a[i][j]%=p; } } } return rt; } }zy[MAXN]; viar ans; void slv(){ scanf("%lld%lld",&n,&m);n++;m++; ans.x=1;ans.y=n; for(int i=1;i<=n;i++)ans.a[1][i]=0; ans.a[1][1]=1; for(int i=0;(1<<i)<=m;i++){ if(m&(1<<i)){ zy[i].y=n; zy[i].x=n; ans=ans*zy[i]; } } printf("%lld\n",ans.a[1][n]); } signed main(){ scanf("%lld%lld%lld",&_,&q,&p); for(int i=1;i<=110;i++)zy[0].a[1][i]=1; zy[0].x=110;zy[0].y=110; for(int i=2;i<=110;i++){ for(int j=i;j<=110;j++){ zy[0].a[i][j]=zy[0].a[i-1][j]*q%p; } } for(int i=1;i<=60;i++){ zy[i]=zy[i-1]*zy[i-1]; } while(_--)slv(); return 0; }