#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 add(int bg,int ed){ cnt[bg]++;cnt[ed+1]--; } inline 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++)while(!vec[i].empty()){ int p=vec[i].back();vec[i].pop_back(); pii ps=decode(p);int x=ps.fi,y=ps.se; if(vis[x][y]) continue;vis[x][y]=1; w[0]=1;w[1]=1;w[2]=To[y]-To[y-1];w[3]=To[y+1]-To[y]; for(int j=0;j<4;j++){ int nx=x+dx[j],ny=y+dy[j]; if(nx<1||ny<1||nx>n||ny>len) continue; if(vis[nx][ny]) continue; //cout<<x<<' '<<y<<' '<<nx<<' '<<ny<<' '<<dis[x][y]+w<<endl; if(dis[x][y]+w[j]<dis[nx][ny]){ dis[nx][ny]=dis[x][y]+w[j]; vec[dis[nx][ny]].push_back(incode(nx,ny)); } } } 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; }