#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define ll long long #define ull unsigned ll #define uint unsigned int using namespace std; const int N=1e5+10; const uint mod=2.5e9+1; uint qp(uint a,uint b){ uint x=1; while(b){ if(b&1) x=1ull*x*a%mod; b>>=1;a=1ull*a*a%mod; }return x; } const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};int w[4]; map<pii,int> mp; map<int,int> to; int pos[N]; ll cnt[N<<1];uint inv[N<<1]; int n,m,k,len=0; int dis[N][1005],To[1005]; bool vis[N][1005]; vector<int> vec[N<<1]; inline int incode(int a,int b){ return a+(b-1)*n; } inline pii decode(int a){ return mk((a-1)%n+1,(a-1)/n+1); } inline void upd(int x,int y,int d){ if(!vis[x][y]){ if(d<dis[x][y]){ dis[x][y]=d; vec[d].push_back(incode(x,y)); } } } inline void add(int bg,int ed){ cnt[bg]++;cnt[ed+1]--; } void slv(){ cin>>n>>m>>k;mp.clear();to.clear();len=0; for(int i=0;i<=n+m;i++) cnt[i]=0; for(int i=1;i<=k;i++){ int x,y;cin>>x>>y; mp[mk(x,y)]=1;to[y]=1; } for(auto &ed:to) ed.se=++len,To[len]=ed.fi; for(int i=1;i<=n;i++)for(int j=1;j<=len;j++) dis[i][j]=1e9,vis[i][j]=0; for(int i=0;i<=n+m;i++) vec[i].clear(),cnt[i]=0; for(auto ed:mp) vec[0].push_back(incode(ed.fi.fi,to[ed.fi.se])), dis[ed.fi.fi][to[ed.fi.se]]=0; for(int i=0;i<=n+m;i++)for(auto p:vec[i]){ pii ps=decode(p);int x=ps.fi,y=ps.se; if(vis[x][y]) continue;vis[x][y]=1; if(x-1>=1) upd(x-1,y,dis[x][y]+1); if(x+1<=n) upd(x+1,y,dis[x][y]+1); if(y-1>=1) upd(x,y-1,dis[x][y]+To[y]-To[y-1]); if(y+1<=len)upd(x,y+1,dis[x][y]+To[y+1]-To[y]); } for(int i=1;i<=n;i++)for(int j=1;j<=len;j++)add(dis[i][j],dis[i][j]); for(int i=1;i<=n;i++){ for(int j=1;j<len;j++){ int ps=(To[j]+To[j+1]+dis[i][j+1]-dis[i][j])/2; add(dis[i][j]+1,dis[i][j]+(ps-To[j])); add(dis[i][j+1]+1,dis[i][j+1]+(To[j+1]-ps-1)); } add(dis[i][1]+1,dis[i][1]+(To[1]-1)); add(dis[i][len]+1,dis[i][len]+(m-To[len])); } for(int i=1;i<=n+m;i++)cnt[i]+=cnt[i-1]; for(int i=1;i<=n+m;i++)cnt[i]+=cnt[i-1]; int lim=min((ll)(n+m),1ll*n*m-1); inv[0]=1ull*n*m%mod; for(int i=1;i<=lim;i++) inv[i]=(1ull*n*m-i)*inv[i-1]%mod; inv[lim]=qp(inv[lim],mod-2); for(int i=lim-1;i>=0;i--){ ll val=inv[i]; inv[i]=(1ull*n*m-(i+1))*inv[i+1]%mod; inv[i+1]=1ull*inv[i+1]*val%mod; } uint ans=1; for(int i=0;i<=lim;i++){ ans=ans*(cnt[i]-i)%mod*inv[i]%mod; //cout<<inv[i]<<' '<<(1ll*n*m-i)%mod<<endl; //assert(inv[i]==qp((1ll*n*m-i)%mod,mod-2)); }cout<<ans<<endl; } int main(){ //freopen("snowball.in","r",stdin); //freopen("snowball.out","w",stdout); int t;cin>>t; while(t--) slv(); return 0; }