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>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#include <unistd.h>
#define dibs reserve
#define OVER9000 1034567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

cat encode(int a, int b, int c) {
	return ((1LL*a)<<40)+((1LL*b)<<20)+c;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int H, W, N;
	cin >> H >> W >> N;
	vector< pair<int, int> > bl(N);
	map<int, int> Mx, My;
	Mx[0] =Mx[H] =0;
	My[0] =My[W] =0;
	for(int i =0; i < N; i++) {
		cin >> bl[i].ff >> bl[i].ss;
		Mx[bl[i].ff] =Mx[bl[i].ff+1] =0;
		My[bl[i].ss] =My[bl[i].ss+1] =0;
	}
	int mx =0, my =0;
	vector< pair<int,int> > Ix, Iy;
	int last =-1;
	ALL_THE(Mx, it) {
		it->ss =mx++;
		if(last >= 0) Ix.push_back(make_pair(last, it->ff));
		last =it->ff;
	}
	last =-1;
	ALL_THE(My, it) {
		it->ss =my++;
		if(last >= 0) Iy.push_back(make_pair(last, it->ff));
		last =it->ff;
	}
	vector< vector<bool> > BL(mx, vector<bool>(my, 0));
	for(int i =0; i < N; i++) BL[Mx[bl[i].ff]][My[bl[i].ss]] =1;
	mx--, my--;

	cat mod =1000000007;
	// sum of Manhattan distances
	cat ans =((1LL*(H-1)*H*(H+1)/6)%mod*W%mod*W+(1LL*(W-1)*W*(W+1)/6)%mod*H%mod*H)%mod;
	for(int i =0; i < N; i++) {
		cat sum =0;
		sum =(sum+(1LL*bl[i].ff*(bl[i].ff+1)/2+1LL*(H-1-bl[i].ff)*(H-bl[i].ff)/2)%mod*W)%mod;
		sum =(sum+(1LL*bl[i].ss*(bl[i].ss+1)/2+1LL*(W-1-bl[i].ss)*(W-bl[i].ss)/2)%mod*H)%mod;
		for(int j =0; j < N; j++)
			sum -=abs(bl[j].ff-bl[i].ff)+abs(bl[j].ss-bl[i].ss);
		ans =(ans-sum)%mod;
	}
	for(int i =0; i < N; i++) for(int j =0; j < i; j++)
		ans -=abs(bl[j].ff-bl[i].ff)+abs(bl[j].ss-bl[i].ss);

	vector< vector< vector<int> > > Dx(mx, vector< vector<int> >(my, vector<int>(my, OVER9000)));
	vector< vector< vector<int> > > Dy(my, vector< vector<int> >(mx, vector<int>(mx, OVER9000)));
	priority_queue< pair<int, cat>, vector< pair<int, cat> >, greater< pair<int, cat> > > qx, qy;
	for(int i =0; i < mx; i++) for(int j =0; j < my; j++) if(!BL[i][j]) {
		Dx[i][j][j] =Dy[j][i][i] =0;
		qx.push(make_pair(0, encode(i, j, j)));
		qy.push(make_pair(0, encode(j, i, i)));
	}

	while(!qx.empty()) {
		pair<int, cat> p =qx.top();
		qx.pop();
		int x =p.ss>>40, y1 =(p.ss>>20)&((1LL<<20)-1), y2 =p.ss&((1LL<<20)-1);
		if(Dx[x][y1][y2] != p.ff) continue;
		// +1, in row-direction
		if(y1 > 0 && !BL[x][y1-1] && Dx[x][y1-1][y2] > Dx[x][y1][y2]) {
			Dx[x][y1-1][y2] =Dx[x][y1][y2];
			qx.push(make_pair(Dx[x][y1-1][y2], encode(x, y1-1, y2)));
		}
		if(y2+1 < my && !BL[x][y2+1] && Dx[x][y1][y2+1] > Dx[x][y1][y2]) {
			Dx[x][y1][y2+1] =Dx[x][y1][y2];
			qx.push(make_pair(Dx[x][y1][y2+1], encode(x, y1, y2+1)));
		}
		// -1 in the row-direction
		if(y1 < y2 && !BL[x][y1+1] && Dx[x][y1+1][y2] > Dx[x][y1][y2]+1) {
			Dx[x][y1+1][y2] =Dx[x][y1][y2]+1;
			qx.push(make_pair(Dx[x][y1+1][y2], encode(x, y1+1, y2)));
		}
		if(y1 < y2 && !BL[x][y2-1] && Dx[x][y1][y2-1] > Dx[x][y1][y2]+1) {
			Dx[x][y1][y2-1] =Dx[x][y1][y2]+1;
			qx.push(make_pair(Dx[x][y1][y2-1], encode(x, y1, y2-1)));
		}
		// +1,+1 in the same col-direction
		if(x > 0 && !BL[x-1][y1] && !BL[x-1][y2] && Dx[x-1][y1][y2] > Dx[x][y1][y2]+1) {
			Dx[x-1][y1][y2] =Dx[x][y1][y2]+1;
			qx.push(make_pair(Dx[x-1][y1][y2], encode(x-1, y1, y2)));
		}
		if(x+1 < mx && !BL[x+1][y1] && !BL[x+1][y2] && Dx[x+1][y1][y2] > Dx[x][y1][y2]+1) {
			Dx[x+1][y1][y2] =Dx[x][y1][y2]+1;
			qx.push(make_pair(Dx[x+1][y1][y2], encode(x+1, y1, y2)));
		}
	}
	while(!qy.empty()) {
		pair<int, cat> p =qy.top();
		qy.pop();
		int y =p.ss>>40, x1 =(p.ss>>20)&((1LL<<20)-1), x2 =p.ss&((1LL<<20)-1);
		if(Dy[y][x1][x2] != p.ff) continue;
		// +1, in row-direction
		if(x1 > 0 && !BL[x1-1][y] && Dy[y][x1-1][x2] > Dy[y][x1][x2]) {
			Dy[y][x1-1][x2] =Dy[y][x1][x2];
			qy.push(make_pair(Dy[y][x1-1][x2], encode(y, x1-1, x2)));
		}
		if(x2+1 < mx && !BL[x2+1][y] && Dy[y][x1][x2+1] > Dy[y][x1][x2]) {
			Dy[y][x1][x2+1] =Dy[y][x1][x2];
			qy.push(make_pair(Dy[y][x1][x2+1], encode(y, x1, x2+1)));
		}
		// -1 in the row-direction
		if(x1 < x2 && !BL[x1+1][y] && Dy[y][x1+1][x2] > Dy[y][x1][x2]+1) {
			Dy[y][x1+1][x2] =Dy[y][x1][x2]+1;
			qy.push(make_pair(Dy[y][x1+1][x2], encode(y, x1+1, x2)));
		}
		if(x1 < x2 && !BL[x2-1][y] && Dy[y][x1][x2-1] > Dy[y][x1][x2]+1) {
			Dy[y][x1][x2-1] =Dy[y][x1][x2]+1;
			qy.push(make_pair(Dy[y][x1][x2-1], encode(y, x1, x2-1)));
		}
		// +1,+1 in the same col-direction
		if(y > 0 && !BL[x1][y-1] && !BL[x2][y-1] && Dy[y-1][x1][x2] > Dy[y][x1][x2]+1) {
			Dy[y-1][x1][x2] =Dy[y][x1][x2]+1;
			qy.push(make_pair(Dy[y-1][x1][x2], encode(y-1, x1, x2)));
		}
		if(y+1 < my && !BL[x1][y+1] && !BL[x2][y+1] && Dy[y+1][x1][x2] > Dy[y][x1][x2]+1) {
			Dy[y+1][x1][x2] =Dy[y][x1][x2]+1;
			qy.push(make_pair(Dy[y+1][x1][x2], encode(y+1, x1, x2)));
		}
	}

	for(int x =0; x < mx; x++)
		for(int y1 =0; y1 < my; y1++) for(int y2 =0; y2 < y1; y2++)
			Dx[x][y1][y2] =Dx[x][y2][y1];
	for(int y =0; y < my; y++)
		for(int x1 =0; x1 < mx; x1++) for(int x2 =0; x2 < x1; x2++)
			Dy[y][x1][x2] =Dy[y][x2][x1];

	vector< vector<int> > D(mx*my, vector<int>(mx*my, OVER9000));
	for(int i =0; i < mx; i++) for(int j =0; j < my; j++) if(!BL[i][j]) {
		D[i*my+j][i*my+j] =0;
		for(int k =0; k < mx; k++) if(!BL[k][j])
			D[i*my+j][k*my+j] =D[k*my+j][i*my+j] =2*Dy[j][i][k]+abs(i-k);
		for(int k =0; k < my; k++) if(!BL[i][k])
			D[i*my+j][i*my+k] =D[i*my+k][i*my+j] =2*Dx[i][j][k]+abs(j-k);
	}

	// Dijkstra from everywhere
	queue<int> q;
	vector<bool> vis(mx*my);
	int dx[] ={1, -1, 0, 0};
	int dy[] ={0, 0, 1, -1};
	for(int i =0; i < mx*my; i++) if(!BL[i/my][i%my]) {
		q.push(i);
		for(int j =0; j < mx*my; j++) vis[j] =0;
		vis[i] =1;
		while(!q.empty()) {
			int x =q.front()/my, y =q.front()%my, p =q.front();
			for(int k =0; k < 4; k++) if(x+dx[k] >= 0 && y+dy[k] >= 0 && x+dx[k] < mx && y+dy[k] < my) {
				if(vis[p+dx[k]*my+dy[k]] || BL[x+dx[k]][y+dy[k]]) continue;
				D[i][p+dx[k]*my+dy[k]] =D[i][p]+1;
				vis[p+dx[k]*my+dy[k]] =1;
				q.push(p+dx[k]*my+dy[k]);
			}
			q.pop();
		}
//		for(int j =0; j < mx*my; j++) for(int k =0; k < mx*my; k++)
//			if(D[j][k] > D[j][i]+D[i][k]) D[j][k] =D[j][i]+D[i][k];
	}

	for(int x1 =0; x1 < mx; x1++) for(int y1 =0; y1 < my; y1++)
		for(int x2 =0; x2 <= x1; x2++) for(int y2 =0; y2 < my; y2++) {
			if(x2 == x1 && y2 >= y1) continue;
			if(D[x1*my+y1][x2*my+y2] == OVER9000) continue;
			cat cnt1 =1LL*(Ix[x1].ss-Ix[x1].ff)*(Iy[y1].ss-Iy[y1].ff)%mod;
			cat cnt2 =1LL*(Ix[x2].ss-Ix[x2].ff)*(Iy[y2].ss-Iy[y2].ff)%mod;
			ans =(ans+(cnt1*cnt2)%mod*(D[x1*my+y1][x2*my+y2]-abs(x1-x2)-abs(y1-y2)))%mod;
		}

	ans %=mod;
	if(ans < 0) ans +=mod;
	cout << ans << "\n";
	return 0;}

// look at my code
// my code is amazing
