#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair bool AAA; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} const int MAXN=2000010,N=1010,M=50010,Mod=2500000001,inf=1e9; int Pow(int x,int y){int rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod,y>>=1;}return rt;} void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;} int n,m,k,a[MAXN],b[MAXN],p[MAXN]; void sol1(){ int x=a[1],y=b[1]; for(int i=1;i<=m;i++){ p[0+abs(y-i)]++,p[1+abs(y-i)]++; p[x+abs(y-i)]--,p[n-x+1+abs(y-i)]--; } for(int i=1;i<=n+m;i++)p[i]+=p[i-1]; } int vis[MAXN]; int mx[4]={1,-1,0,0},my[4]={0,0,-1,1}; queue<pii>Q; int mp(int x,int y){return (x-1)*m+y;} pii pm(int x){return mk((x-1)/m+1,(x-1)%m+1);} void sol2(){ for(int i=1;i<=n*m;i++)vis[i]=-1; for(int i=1;i<=k;i++)if(vis[mp(a[i],b[i])]==-1)Q.push(mk(a[i],b[i])),vis[mp(a[i],b[i])]=0; while(!Q.empty()){ int x=Q.front().fr,y=Q.front().sc;Q.pop(); p[vis[mp(x,y)]]++; for(int o=0;o<4;o++){ int nx=x+mx[o],ny=y+my[o]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&vis[mp(nx,ny)]==-1)vis[mp(nx,ny)]=vis[mp(x,y)]+1,Q.push(mk(nx,ny)); } } } unordered_map<int,int>val[MAXN]; int f[M][N]; bool is[M][N]; void sol3(){ for(int i=1;i<=n;i++)val[i].clear(); for(int i=1;i<=k;i++)val[a[i]][b[i]]=1; k+=2,b[k]=m,b[k-1]=1; sort(b+1,b+k+1); int km=unique(b+1,b+k+1)-b-1; for(int i=1;i<=n;i++)for(int j=1;j<=km;j++)is[i][j]=val[i].count(b[j]); for(int i=0;i<=n+1;i++)for(int j=0;j<=km+1;j++)f[i][j]=inf; for(int i=1;i<=n;i++)for(int j=1;j<=km;j++){ if(is[i][j])f[i][j]=0; else f[i][j]=min(f[i-1][j]+1,f[i][j-1]+b[j]-b[j-1]); } for(int i=1;i<=n;i++)for(int j=km;j>=1;j--){ if(is[i][j])f[i][j]=0; else f[i][j]=min({f[i][j],f[i-1][j]+1,f[i][j+1]+b[j+1]-b[j]}); } for(int i=n;i>=1;i--)for(int j=1;j<=km;j++){ if(is[i][j])f[i][j]=0; else f[i][j]=min({f[i][j],f[i+1][j]+1,f[i][j-1]+b[j]-b[j-1]}); } for(int i=n;i>=1;i--)for(int j=km;j>=1;j--){ if(is[i][j])f[i][j]=0; else f[i][j]=min({f[i][j],f[i+1][j]+1,f[i][j+1]+b[j+1]-b[j]}); } // for(int i=1;i<=n;i++,cout<<endl)for(int j=1;j<=km;j++)cout<<f[i][j]<<" "; b[km+1]=m+1; int tmp=0; for(int i=1;i<=n;i++)for(int j=1;j<=km;j++){ int x=f[i][j],y=f[i][j+1]+1,s=b[j+1]-b[j]; if(x>y)swap(x,y); if(x+s-1<=y)p[x]++,p[x+s]--,tmp+=s; else p[x]++,p[y]++,p[(s-(y-x))/2+y]--,p[(s-(y-x)-1)/2+y+1]--,tmp+=(s-(y-x))/2+y+1-x+(s-(y-x)-1)/2+y+2-y; } for(int i=1;i<=n+m;i++)p[i]+=p[i-1]; } void slv(){ n=read(),m=read(),k=read(); for(int i=1;i<=k;i++)a[i]=read(),b[i]=read(); sol3(); int ans=1,ansn=1,sum=0; for(int i=0;i<=n+m-1;i++){ sum+=p[i]; ans=ans*(sum-i)%Mod; ansn=ansn*(n*m-i)%Mod; p[i]=0; } printf("%lld\n",ans*Pow(ansn,Mod-2)%Mod); } bool BBB; signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); int _=read();while(_--) slv(); // cerr<<(clock()*1.0)/CLOCKS_PER_SEC<<"s\n"; // cerr<<((&AAA)-(&BBB))/1024.0/1024<<"MB\n"; return 0; }