#include <bits/stdc++.h> #define PII pair<int,int> #define LL long long using namespace std; const int MAXN=5005; int T,N,M,Q,P; LL dp[MAXN][MAXN]; LL po[MAXN]; struct Matrix { LL v[105][105]; void Set() { for(int i=0;i<=N;i++) for(int j=0;j<=N;j++) v[i][j]=0; } }; Matrix Mul(Matrix x,Matrix y) { Matrix res; res.Set(); for(int i=0;i<=N;i++) { for(int j=0;j<=N;j++) { if(i>1&&j<i) { res.v[i][j]=0; continue; } for(int k=0;k<=N;k++) { res.v[i][j]=(res.v[i][j]+x.v[i][k]*y.v[k][j])%P; } } } return res; } void Print(Matrix m) { for(int i=0;i<=N;i++) { for(int j=0;j<=N;j++) printf("%lld ",m.v[i][j]); puts(""); } puts("-----"); } Matrix QPow(Matrix base,int po) { Matrix res=base; //Print(res); po--; while(po) { if(po&1) res=Mul(res,base); base=Mul(base,base); po>>=1; //Print(res); } //Print(res); return res; } int main() { freopen("walk.in","r",stdin); freopen("walk.out","w",stdout); scanf("%d %d %d",&T,&Q,&P); po[0]=1; for(int i=1;i<=5000;i++) po[i]=po[i-1]*Q%P; dp[0][0]=1; for(int i=0;i<=5000;i++) { for(int j=0;j<=5000;j++) { if(i==0&&j==0) continue; if(i>0) dp[i][j]=(dp[i][j]+dp[i-1][j]*po[j])%P; if(j>0) dp[i][j]=(dp[i][j]+dp[i][j-1])%P; } } while(T--) { scanf("%d %d",&N,&M); if(N<=5000&&M<=5000) { printf("%lld\n",dp[N][M]); continue; } if(M==0) { puts("1"); continue; } Matrix m; m.Set(); for(int i=0;i<=N;i++) { for(int j=i;j<=N;j++) { m.v[i][j]=po[i]; } } // Print(m); m=QPow(m,M); //Print(m); LL ans=0; for(int i=0;i<=N;i++) ans+=m.v[i][N]; printf("%lld\n",ans%P); } return 0; }