#include<bits/stdc++.h> #include<bits/extc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double db; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=2e5+10; int t,p,q,d; inline int qp(int a,int b){ int res=1; for(;b;b>>=1,a=a*1llu*a%p)if(b&1)res=res*1llu*a%p; return res; } int fac[maxn],ifac[maxn],qfac[maxn],iqfac[maxn]; int binom(int n,int m){ if(n<p&&m<p){ if(n>m)return 0; return fac[m]*1llu*ifac[m-n]%p*ifac[n]%p; } return binom(n/p,m/p)*1llu*binom(n%p,m%p)%p; } int qbinom(int n,int m){ if(n<d&&m<d){ if(n>m)return 0; return qfac[m]*1llu*iqfac[m-n]%p*iqfac[n]%p; } return binom(n/d,m/d)*1llu*qbinom(n%d,m%d)%p; } void slv(){ t=read(),q=read(),p=read(); d=1;for(;qp(q,d)!=1;d++); fac[0]=ifac[0]=1;up(i,1,p-1)ifac[i]=qp(fac[i]=fac[i-1]*1llu*i%p,p-2); qfac[0]=iqfac[0]=1;up(i,1,d-1)iqfac[i]=qp(qfac[i]=qfac[i-1]*1llu*(qp(q,i)-1)%p*qp(q-1,p-2)%p,p-2); for(;t--;){ int n=read(),m=read(); if(q==1)printf("%d\n",binom(n,n+m)); else printf("%d\n",qbinom(n,n+m)); } } int main(){ // freopen("1.in","r",stdin),freopen("1.out","w",stdout); slv(); return 0; }