#include<bits/stdc++.h> #define int long long using namespace std; const int N=2007; int n,m,mod; int Fac[N*(N+2)+7],iFac[N*(N+2)+7]; inline int qpow(int a,int b){ int Ans=1; while(b){ if(b&1)Ans=Ans*a%mod; a=a*a%mod; b>>=1; }return Ans; } inline void Add(int &a,int b){a+=b;(a>=mod?a-=mod:a);} inline void Dec(int &a,int b){a-=b;(a<0?a+=mod:a);} inline void Init(){ Fac[0]=iFac[0]=iFac[1]=1; for(int i=1;i<=4004000;i++)Fac[i]=Fac[i-1]*i%mod; for(int i=2;i<=4004000;i++)iFac[i]=(mod-mod/i)*iFac[mod%i]%mod; for(int i=2;i<=4004000;i++)(iFac[i]*=iFac[i-1])%=mod; }inline int C(int n,int m){ return (n<m||m<0?0:Fac[n]*iFac[m]%mod*iFac[n-m]%mod); }inline void slv(){ cin>>n>>m; int S2=0; for(int i=0;i<=n;i++){ int V=C(2*n,i)*C(n*m-i*(m+1)+2*n-1,2*n-1)%mod; (i&1?Dec(S2,V):Add(S2,V)); if(n*m-i*(m+1)<0)break; }(S2*=qpow(m+1,mod-1-2*n))%=mod; cout<<(mod+1-S2)%mod*(mod+1>>1)%mod<<endl; return; } signed main(){ cin>>mod;Init(); int T;cin>>T; while(T--)slv(); }