#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]--; } 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) dis[ed.fi.fi][to[ed.fi.se]]=0; for(int i=1;i<=n;i++)for(int j=1;j<len;j++) dis[i][j+1]=min(dis[i][j+1],dis[i][j]+To[j+1]-To[j]); for(int i=1;i<=n;i++)for(int j=len-1;j>=1;j--) dis[i][j]=min(dis[i][j],dis[i][j+1]+To[j+1]-To[j]); for(int i=1;i<n;i++)for(int j=1;j<=len;j++)dis[i+1][j]=min(dis[i+1][j],dis[i][j]+1); for(int i=n-1;i>=1;i--)for(int j=1;j<=len;j++)dis[i][j]=min(dis[i][j],dis[i+1][j]+1); 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; }