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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=30;
const int MAXDIM=2*MAXN+1;
const int MOD=1000000007;
const int INV2=(MOD+1)/2;
const int DX[]={-1,0,+1,0},DY[]={0,+1,0,-1};

int h,w,n;
int px[MAXN],py[MAXN];

int xx[2*MAXN+2],yy[2*MAXN+2],nxx,nyy;

bool blocked[MAXDIM][MAXDIM];
int cnt[MAXDIM][MAXDIM];

int dst[MAXDIM][MAXDIM];
int qx[MAXDIM*MAXDIM],qy[MAXDIM*MAXDIM],qhead,qtail;
void upd(int x,int y,int d) { if(dst[x][y]!=INT_MAX) return; dst[x][y]=d; qx[qhead]=x,qy[qhead]=y,++qhead; }

bool reachall;
int solvecompressed() {
	int ret=0; reachall=true;
	//REP(x,nxx-1) { REP(y,nyy-1) printf("%c",blocked[x][y]?'#':'.'); puts(""); }
	REP(sx,nxx-1) REP(sy,nyy-1) if(!blocked[sx][sy]) {
		REP(x,nxx-1) REP(y,nyy-1) dst[x][y]=INT_MAX; qhead=qtail=0;
		upd(sx,sy,0);
		while(qtail<qhead) {
			int x=qx[qtail],y=qy[qtail]; ++qtail;
			REP(k,4) {
				int nx=x+DX[k],ny=y+DY[k]; if(nx<0||nx>=nxx-1||ny<0||ny>=nyy-1||blocked[nx][ny]) continue;
				upd(nx,ny,dst[x][y]+1);
			}
		}
		REP(x,nxx-1) REP(y,nyy-1) if(!blocked[x][y]) {
			if(dst[x][y]==INT_MAX) reachall=false;
			//printf("(%d,%d)->(%d,%d) : %d * %d * %d\n",sx,sy,x,y,cnt[sx][sy],cnt[x][y],dst[x][y]);
			ret=(ret+(ll)cnt[sx][sy]*cnt[x][y]%MOD*dst[x][y])%MOD;
		}
	}
	//printf("%d\n",ret);
	ret=(ll)ret*INV2%MOD;
	return ret;
}

int solve() {
	nxx=0; xx[nxx++]=0,xx[nxx++]=h; REP(i,n) xx[nxx++]=px[i],xx[nxx++]=px[i]+1; sort(xx,xx+nxx); nxx=unique(xx,xx+nxx)-xx; REP(i,n) px[i]=lower_bound(xx,xx+nxx,px[i])-xx;
	nyy=0; yy[nyy++]=0,yy[nyy++]=w; REP(i,n) yy[nyy++]=py[i],yy[nyy++]=py[i]+1; sort(yy,yy+nyy); nyy=unique(yy,yy+nyy)-yy; REP(i,n) py[i]=lower_bound(yy,yy+nyy,py[i])-yy;

	REP(x,nxx-1) REP(y,nyy-1) blocked[x][y]=false,cnt[x][y]=(ll)(xx[x+1]-xx[x])*(yy[y+1]-yy[y])%MOD;
	REP(i,n) blocked[px[i]][py[i]]=true;

	int ret=solvecompressed();

	REP(x,nxx-1) {
		int len=xx[x+1]-xx[x]; if(len==1) continue;
		int a=(ll)(len-1)*len*(len+1)/6%MOD;
		int b=(ll)w*w%MOD;
		int c=(ll)len*(len-1)/2%MOD;
		int lft=0,rgt=0; REP(cx,nxx-1) REP(cy,nyy-1) if(!blocked[cx][cy]) if(cx<x) lft=(lft+cnt[cx][cy])%MOD; else if(cx>x) rgt=(rgt+cnt[cx][cy])%MOD;
		//printf("cnt=%d a=%d b=%d c=%d lft=%d rgt=%d\n",len,a,b,c,lft,rgt);
		ret=(ret+(ll)a*b)%MOD;
		ret=(ret+(ll)lft*rgt%MOD*(len-1))%MOD;
		ret=(ret+(ll)(lft+rgt)*c%MOD*w)%MOD;
	}
	REP(y,nyy-1) {
		int len=yy[y+1]-yy[y]; if(len==1) continue;
		int a=(ll)(len-1)*len*(len+1)/6%MOD;
		int b=(ll)h*h%MOD;
		int c=(ll)len*(len-1)/2%MOD;
		int lft=0,rgt=0; REP(cx,nxx-1) REP(cy,nyy-1) if(!blocked[cx][cy]) if(cy<y) lft=(lft+cnt[cx][cy])%MOD; else if(cy>y) rgt=(rgt+cnt[cx][cy])%MOD;
		//printf("cnt=%d a=%d b=%d c=%d lft=%d rgt=%d\n",len,a,b,c,lft,rgt);
		ret=(ret+(ll)a*b)%MOD;
		ret=(ret+(ll)lft*rgt%MOD*(len-1))%MOD;
		ret=(ret+(ll)(lft+rgt)*c%MOD*h)%MOD;
	}
	return ret;
}

void run() {
	scanf("%d%d%d",&h,&w,&n);
	REP(i,n) scanf("%d%d",&px[i],&py[i]);
	printf("%d\n",solve());
}

int main() {
	run();
	return 0;
}
