//50pts #include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=5010,N=101,LG=31;int Mod; int Pow(int x,int y){int res=1;while(y){if(y&1)res=res*x%Mod;x=x*x%Mod;y>>=1;}return res;} int n,m,q,ans,f[MAXN][MAXN],jc[MAXN]; struct matrix{ int p[N+5][N+5]; int x,y; void init(int X,int Y){ x=X,y=Y; for(int i=0;i<x;i++)for(int j=0;j<y;j++)p[i][j]=0; } matrix operator *(const matrix&G)const{ matrix res; res.init(x,G.y); for(int i=0;i<x;i++){ for(int j=0;j<G.y;j++){ res.p[i][j]=0; for(int k=0;k<y;k++){ res.p[i][j]=(res.p[i][j]+p[i][k]*G.p[k][j]%Mod)%Mod; } } } return res; } }Q,P[LG+2]; void init(){ jc[0]=1; for(int i=1;i<=MAXN-5;i++)jc[i]=jc[i-1]*q%Mod; for(int i=0;i<=MAXN-5;i++)f[0][i]=1; for(int i=1;i<=MAXN-5;i++) for(int j=0;j<=MAXN-5;j++) f[i][j]=(f[i][j-1]+f[i-1][j]*jc[j]%Mod)%Mod; P[0].init(N,N); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ P[0].p[i][j]=i<=j?jc[j]:0; } } for(int i=1;i<LG;i++)P[i]=P[i-1]*P[i-1]; } void slv1(){ printf("%lld\n",f[n][m]); } void slv2(){ Q.init(1,N); Q.p[0][0]=1; for(int i=LG;i>=0;i--)if(m&(1<<i))Q=Q*P[i]; ans=0; for(int i=0;i<=n;i++)ans+=Q.p[0][i],ans%=Mod; printf("%lld\n",ans); } void slv(){ n=read(),m=read(); if(n<=5000&&m<=5000)slv1(); else slv2(); } signed main(){ int _=read();q=read(),Mod=read();init(); while(_--) slv(); return 0; }