#include<bits/stdc++.h> using namespace std; #define int long long #define fls fflush(stdout) template<typename T> inline void read(T &x){x=0;char c=getchar();bool neg=0;while(!isdigit(c)){if(c=='-')neg=1;c=getchar();}while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();if(neg)x=-x;} #define read2(a,b) read(a),read(b) #define read3(a,b,c) read2(a,b),read(c) #define read4(a,b,c,d) read3(a,b,c),read(d) #define read5(a,b,c,d,e) read4(a,b,c,d),read(e) #define read6(a,b,c,d,e,f) read5(a,b,c,d,e),read(f) int mod,n,m,fact[4000005],inv[4000005]; int C(int x,int y){ if(x<y)return 0; return fact[x]*inv[y]%mod*inv[x-y]%mod; } int qp(int x,int y){ int res=1; while(y){ if(y&1)res*=x,res%=mod; x*=x,x%=mod; y>>=1; } return res; } void slv(){ read2(n,m); int ans=0; // cout<<"C(3,1) for(int i=0,sgn=1;i<=n+n;i++,sgn=-sgn){ ans+=sgn*C(n+n,i)*C(n*m-(m+1)*i+n+n-1,n+n-1)%mod; } // cout<<ans<<endl; cout<<((1-(ans%mod+mod)%mod*qp(qp(m+1,mod-2),n+n)%mod)*((mod+1)/2)%mod+mod)%mod<<endl; } signed main(){ //freopen("slpjbh.in","r",stdin); //freopen("slpjbh.out","w",stdout); read(mod); fact[0]=1; for(int i=1;i<=4000000;i++)fact[i]=fact[i-1]*i%mod; inv[4000000]=qp(fact[4000000],mod-2); for(int i=3999999;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod; int T;read(T);while(T--) slv(); return 0; }