#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 p_b push_back using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; const int maxn=4.1e6+10; 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; } int mod,jc[maxn],jc_inv[maxn]; int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1llu*a%mod; a=a*1llu*a%mod,b>>=1; }return res; } void init(){ int n=4.1e6; jc[0]=1;up(i,1,n)jc[i]=jc[i-1]*1llu*i%mod; jc_inv[n]=qp(jc[n],mod-2);down(i,n,1)jc_inv[i-1]=jc_inv[i]*1llu*i%mod; } int C(int n,int m){return jc[m]*1llu*jc_inv[m-n]%mod*1llu*jc_inv[n]%mod;} int F(int n,int m,int s){ int res=0; up(i,0,min(n,s/(m+1))){ int va=C(i,n)*1llu*C(n-1,s-i*(m+1)+n-1)%mod; if(i&1)va=mod-va;(res+=va)%=mod; } return res; } void slv(){ int n=read(),m=read(); int ans=F(2*n,m,n*m),all=qp(m+1,2*n),prob=ans*1llu*qp(all,mod-2)%mod; prob=(mod+1-prob)*1llu*((mod+1)/2)%mod; printf("%d\n",prob); } int main(){ //freopen("pr.in","r",stdin),freopen("pr.out","w",stdout); mod=read();init();int t=read();while(t--)slv(); return 0; }