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 mod 1000000007
using namespace std;
bool vh[1000005],vw[1000005];
int bh[1000005],bw[1000005];
int nh[1000005],nw[1000005];
int h,w,n,x[31],y[31],c1=0,c2=0;
int kh[105],kw[105],wgt[65][65];
int dis[65][65],que[10005][2],l=1,r=0;
bool ban[65][65];
inline int mul(int a,int b)
{return 1ll*a*b%mod;}
inline int sub(int a,int b)
{return (a-b<0?a-b+mod:a-b);}
inline bool ok(int a,int b)
{if (a<=0||a>c1||b<=0||b>c2||ban[a][b]) return 0;
return 1;
}
int main (){
	int i,j,k,l,ans=0;
	scanf ("%d%d%d",&h,&w,&n);
	for (i=1;i<=n;i++)
	{scanf ("%d%d",&x[i],&y[i]);
	x[i]++;y[i]++;
	nh[x[i]]++;nw[y[i]]++;
	vh[x[i]]=vw[y[i]]=1;
	}
	bh[1]=++c1;kh[1]++;
	int lo=0,tot=mul(h,w)-n;
	if (tot<0) tot+=mod;
	for (i=2;i<=h;i++)
	{lo+=(w-nh[i-1]);
	if (lo>=mod) lo-=mod;
	if ((!vh[i-1])&&(!vh[i]))
	{ans+=mul(lo,sub(tot,lo));
	if (ans>=mod) ans-=mod;
	bh[i]=bh[i-1];kh[c1]++;
	}
	else {bh[i]=++c1;kh[c1]=1;}
	}
	bw[1]=++c2;kw[1]++;
	lo=0;tot=mul(h,w)-n;
	if (tot<0) tot+=mod;
	for (i=2;i<=w;i++)
	{lo+=(h-nw[i-1]);
	if (lo>=mod) lo-=mod;
	if ((!vw[i-1])&&(!vw[i]))
	{ans+=mul(lo,sub(tot,lo));
	if (ans>=mod) ans-=mod;
	bw[i]=bw[i-1];kw[c2]++;
	}
	else {bw[i]=++c2;kw[c2]=1;}
	}
	for (i=1;i<=c1;i++)
	{for (j=1;j<=c2;j++)
	{wgt[i][j]=mul(kh[i],kw[j]);}
	}
	for (i=1;i<=n;i++)
	{ban[bh[x[i]]][bw[y[i]]]=1;}
	ans*=2;
	if (ans>=mod) ans-=mod;
	for (i=1;i<=c1;i++)
	{for (j=1;j<=c2;j++)
	{if (ban[i][j]) continue;
	l=1;r=0;que[++r][0]=i;que[r][1]=j;
	memset (dis,0x7f,sizeof(dis));
	dis[i][j]=0;
	while (l<=r)
	{int a=que[l][0],b=que[l][1];l++;
	if (ok(a-1,b)&&dis[a-1][b]>dis[a][b]+1)
	{dis[a-1][b]=dis[a][b]+1;
	que[++r][0]=a-1;que[r][1]=b;
	}
	if (ok(a+1,b)&&dis[a+1][b]>dis[a][b]+1)
	{dis[a+1][b]=dis[a][b]+1;
	que[++r][0]=a+1;que[r][1]=b;
	}
	if (ok(a-1,b)&&dis[a-1][b]>dis[a][b]+1)
	{dis[a-1][b]=dis[a][b]+1;
	que[++r][0]=a-1;que[r][1]=b;
	}
	if (ok(a,b-1)&&dis[a][b-1]>dis[a][b]+1)
	{dis[a][b-1]=dis[a][b]+1;
	que[++r][0]=a;que[r][1]=b-1;
	}
	if (ok(a,b+1)&&dis[a][b+1]>dis[a][b]+1)
	{dis[a][b+1]=dis[a][b]+1;
	que[++r][0]=a;que[r][1]=b+1;
	}
	}
	int tp=0;
	for (k=1;k<=c1;k++)
	{for (l=1;l<=c2;l++)
	{if (ban[k][l]) continue;
	tp+=mul(dis[k][l],wgt[k][l]);
	if (tp>=mod) tp-=mod;
	}
	}
	tp=mul(tp,wgt[i][j]);
	ans+=tp;
	if (ans>=mod) ans-=mod;
	}
	}
	if (ans&1) ans+=mod;
	printf ("%d\n",ans>>1);
	return 0;
}

	
	