#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back const int MAXN=4000010;int Mod; 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<<1)+(x<<3)+(c^48),c=getchar();return x*f;} int n,m; int ad(int x,int y){return x+y>=Mod?x+y-Mod:x+y;} int Pow(int x,int y){int rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod,y>>=1;}return rt;} int jc[MAXN],ny[MAXN]; int C(int x,int y){return x<0||y<0||x<y?0:jc[x]*ny[y]%Mod*ny[x-y]%Mod;} void slv(){ n=read(),m=read(); int ans=0; for(int i=0;i<=2*n;i++)ans=ad(ans,C(n*m-(m+1)*i+2*n-1,2*n-1)*C(2*n,i)%Mod*(i&1?Mod-1:1)%Mod); ans=ad(Pow(m+1,2*n),Mod-ans)*Pow(2,Mod-2)%Mod; printf("%lld\n",ans*Pow(Pow(m+1,2*n),Mod-2)%Mod); } signed main(){ // freopen("pr.in","r",stdin);freopen("pr.out","w",stdout); Mod=read(); jc[0]=ny[0]=1; for(int i=1;i<=MAXN-5;i++)jc[i]=jc[i-1]*i%Mod,ny[i]=Pow(jc[i],Mod-2); int _=read();while(_--) slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }