#include<bits/stdc++.h> using namespace std; int mod;int n,m; void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;} void Sub(int &a,int b){a-=b;if(a<0) a+=mod;} int qp(int a,int b){ int x=1; while(b){ if(b&1) x=1ll*x*a%mod; b>>=1;a=1ll*a*a%mod; }return x; } const int N=4e6+20,LM=4e6+10; int fac[N],inv[N]; int C(int a,int b){if(a<b) return 0;return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;} void slv(){ cin>>n>>m; int ans=0; for(int i=0;i<=n*2;i++){ int now=1ll*C(2*n,i)*C(n*m-i*(m+1)+2*n-1,2*n-1)%mod; if(i&1) Sub(ans,now);else Add(ans,now); }//cout<<ans<<endl; int all=qp(m+1,2*n); ans=1ll*(all+mod-ans)*qp(2,mod-2)%mod; cout<<1ll*ans*qp(all,mod-2)%mod<<endl; } int main(){ //freopen("pr.in","r",stdin); //freopen("pr.out","w",stdout); int t;cin>>mod>>t; fac[0]=1;for(int i=1;i<=LM;i++) fac[i]=1ll*fac[i-1]*i%mod; inv[LM]=qp(fac[LM],mod-2);for(int i=LM-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; while(t--) slv(); return 0; }