You are given an H \times W grid. The square at the top-left corner will be represented by (0, 0), and the square at the bottom-right corner will be represented by (H-1, W-1).

Of those squares, N squares (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) are painted black, and the other squares are painted white.

Let the shortest distance between white squares A and B be the minimum number of moves required to reach B from A visiting only white squares, where one can travel to an adjacent square sharing a side (up, down, left or right) in one move.

Since there are H × W - N white squares in total, there are _{(H×W-N)}C_2 ways to choose two of the white squares.

For each of these _{(H×W-N)}C_2 ways, find the shortest distance between the chosen squares, then find the sum of all those distances, modulo 1 000 000 007=10^9+7.

Constraints

* 1 \leq H, W \leq 10^6
* 1 \leq N \leq 30
* 0 \leq x_i \leq H-1
* 0 \leq y_i \leq W-1
* If i \neq j, then either x_i \neq x_j or y_i \neq y_j.
* There is at least one white square.
* For every pair of white squares A and B, it is possible to reach B from A visiting only white squares.

Input

Input is given from Standard Input in the following format:


H W
N
x_1 y_1
x_2 y_2
:
x_N y_N


Output

Print the sum of the shortest distances, modulo 10^9+7.

Examples

Input

2 3
1
1 1


Output

20


Input

2 3
1
1 2


Output

16


Input

3 3
1
1 1


Output

64


Input

4 4
4
0 1
1 1
2 1
2 2


Output

268


Input

1000000 1000000
1
0 0


Output

333211937
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
namespace IO
{
    const int sz=1<<15;
    char inbuf[sz],outbuf[sz];
    char *pinbuf=inbuf+sz;
    char *poutbuf=outbuf;
    inline char _getchar()
    {
        if (pinbuf==inbuf+sz)fread(inbuf,1,sz,stdin),pinbuf=inbuf;
        return *(pinbuf++);
    }
    inline void _putchar(char x)
    {
        if (poutbuf==outbuf+sz)fwrite(outbuf,1,sz,stdout),poutbuf=outbuf;
        *(poutbuf++)=x;
    }
    inline void flush()
    {
        if (poutbuf!=outbuf)fwrite(outbuf,1,poutbuf-outbuf,stdout),poutbuf=outbuf;
    }
}
inline int read(){
	int v=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9'){
		v=v*10+c-'0';
		c=getchar();
	}
	return v*f;
}

const int Maxn=35;
const int mod=1e9+7; 
const int Maxm=1e6+5;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int H,W;
int ox[Maxm],oy[Maxm],cx[Maxm],cy[Maxm],Sx[Maxm],Sy[Maxm];
int x[Maxn],y[Maxn],n;
vector<int> hr,wr;
int b[99][99],dist[99][99];
int Wx[99],Wy[99];
int qx[9999],qy[9999],sq,eq;
int h=0,w=0;
void Add(int &X,int Y){
	X+=Y;
	if (X>=mod) X%=mod;
}
int bfs(int x,int y){
	for(int i=0;i<h;i++) for(int j=0;j<w;j++){
		dist[i][j]=-1;
	}
	int cf=1ll*Wx[x]*Wy[y]%mod;
	sq=eq=0;
	qx[eq]=x;qy[eq++]=y;
	dist[x][y]=0;
	int ret=0;
	while (sq<eq){
		int X=qx[sq],Y=qy[sq++];
		for (int i=0;i<4;i++){
			int nx=X+dx[i],ny=Y+dy[i];
			if (nx>=0 && ny>=0 && nx<h && ny<w){
				if (dist[nx][ny]==-1 && !b[nx][ny]){
					dist[nx][ny]=dist[X][Y]+1;
					Add(ret,1ll*cf*Wx[nx]%mod*Wy[ny]%mod*dist[nx][ny]%mod);
					qx[eq]=nx;qy[eq++]=ny;
				}
			}
		}
	}
	return ret;
}
int main(){
	H=read();W=read();n=read();
	for (int i=1;i<=n;i++) x[i]=read(),y[i]=read(),x[i]++,y[i]++;
	ox[1]=ox[H]=1;oy[1]=oy[W]=1;
	for (int i=1;i<=n;i++){
		ox[x[i]]=1;ox[x[i]-1]=1;ox[x[i]+1]=1;
		oy[y[i]]=1;oy[y[i]-1]=1;oy[y[i]+1]=1;
		cx[x[i]]++;cy[y[i]]++;
	}
	for (int i=1;i<=H;i++){
		Sx[i]=Sx[i-1]+cx[i];
	}
	for (int i=1;i<=W;i++){
		Sy[i]=Sy[i-1]+cy[i];
	}
	int ans=0;
	int r=0;
	int bf=0;
	for (int i=1;i<=H;i++){
		if(!ox[i]){
			//Add(ans,row);
			int lf=1ll*(i-1-r)*W%mod-Sx[i-1],rg=1ll*(H-i+1)*W%mod-(Sx[H]-Sx[i]);
			if (lf<0) lf+=mod;
			if (rg<0) rg+=mod;
			Add(ans,1ll*lf*rg%mod);
			Wx[h-1]++;
		}
		else{
			h++;Wx[h-1]=1;hr.pb(i);
		}
	}
	r=0;
	for (int i=1;i<=W;i++){
		if (!oy[i]){
			//Add(ans,col);
			int lf=1ll*(i-1-r)*H%mod-Sy[i-1],rg=1ll*(W-i+1)*H%mod-(Sy[W]-Sy[i]);
			if (lf<0) lf+=mod;
			if (rg<0) rg+=mod;  
			Add(ans,1ll*lf*rg%mod);
			Wy[w-1]++;
		}
		else{
			w++;Wy[w-1]=1;wr.pb(i);
		}
	}
//	cerr<<ans<<endl;
	//cerr<<h<<' '<<w<<
//	cerr<<w<<' '<<h<<endl;
	for(int i=0;i<h;i++){
		for (int j=0;j<w;j++){
			for (int k=1;k<=n;k++){
				if (hr[i]==x[k] && wr[j]==y[k]) b[i][j]=1;
			}
		//	cout<<b[i][j]<<' ';
		}
	//	cout<<endl;
	}
	/*
	for (int i=0;i<h;i++){
		for (int j=0;j<w;j++){
			cout<<1ll*Wx[i]*Wy[j]%mod<<' ';
		}
		cout<<endl;
	}*/
	int ans2=0;
	for (int i=0;i<h;i++){
		for (int j=0;j<w;j++){
			if(!b[i][j]){
			//	cerr<<i<<' '<<j<<endl;
				Add(ans2,bfs(i,j));
			}
		}
	}
	//cerr<<ans2<<endl;
	if (ans2%2==0) ans2/=2;
	else ans2+=mod,ans2/=2;
	Add(ans,ans2);
	printf("%d\n",ans);
	return 0;
}
/*
4 4
0
*/