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>
using namespace std;
const int MAX = 1e6 + 5;
const int mod = 1e9 + 7;
const int dx[] = {0, 0, -1, +1}, dy[] = {-1, +1, 0, 0};

int H, W, n;
int x[70], y[70];
bool mark[70][70];
int cntx, cnty, d[70][70], X[70], Y[70];
int posx[MAX], posy[MAX], cntrow[MAX], cntcol[MAX];
vector<int> zx, zy;
int ans;

void add(int &x, int y) {
	x += y; while(x < 0) x += mod; while(x >= mod) x -= mod;
}

void bfs(int sx, int sy) {
	for (int i = 1; i <= cntx; ++i) for (int j = 1; j <= cnty; ++j) d[i][j] = -1;
	queue< pair<int,int> > q; q.push(make_pair(sx, sy)); d[sx][sy] = 0;
	while(!q.empty()) {
		int x = q.front().first, y = q.front().second; q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int nx = x + dx[dir], ny = y + dy[dir];
			if (nx < 1 || nx > cntx || ny < 1 || ny > cnty || d[nx][ny] != -1) continue;
			if (mark[nx][ny]) continue;
			d[nx][ny] = d[x][y] + 1;
			q.push(make_pair(nx, ny));
		}
	}

	int w = 1LL * X[sx] * Y[sy] % mod;
	for (int i = 1; i <= cntx; ++i) {
		for (int j = 1; j <= cnty; ++j) {
			if (i == sx && j == sy) continue;
			if (d[i][j] == -1) continue;
			int wij = 1LL * X[i] * Y[j] % mod;
			int cur = 1LL * w * wij % mod;
			add(ans, 1LL * d[i][j] * cur % mod);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> H >> W >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> x[i] >> y[i];
		cntrow[x[i]]++;
		cntcol[y[i]]++;
	}
	long long blank = 0;
	for (int row = 0; row < H - 1; ++row) {
		blank += W - cntrow[row];
		if (cntrow[row] == 0 && cntrow[row+1] == 0) 
			add(ans, ( (blank % mod) * ((1LL * H * W - n - blank) % mod) ) % mod);
	}
	blank = 0;
	for (int col = 0; col < W - 1; ++col) {
		blank += H - cntcol[col];
		if (cntcol[col] == 0 && cntcol[col+1] == 0)
			add(ans, ( (blank % mod) * ((1LL * H * W - n - blank) % mod) ) % mod);
	}
	ans = 2LL * ans % mod;

	// compress the cells
	for (int i = 1; i <= n; ++i) zx.push_back(x[i]);
	for (int i = 1; i <= n; ++i) zy.push_back(y[i]);
	sort(zx.begin(), zx.end()); zx.erase(unique(zx.begin(), zx.end()), zx.end());
	sort(zy.begin(), zy.end()); zy.erase(unique(zy.begin(), zy.end()), zy.end());

	for (int i = 0; i < zx.size(); ++i) {
		X[++cntx] = zx[i] - (i == 0 ? -1 : zx[i - 1]) - 1;
		if (X[cntx] <= 0) --cntx;
		X[++cntx] = 1; // zx[i]
		posx[zx[i]] = cntx;
	}
	X[++cntx] = H - zx.back() - 1;
	if (X[cntx] <= 0) --cntx;

	for (int i = 0; i < zy.size(); ++i) {
		Y[++cnty] = zy[i] - (i == 0 ? -1 : zy[i - 1]) - 1;
		if (Y[cnty] <= 0) --cnty;
		Y[++cnty] = 1; // zy[i]
		posy[zy[i]] = cnty;
	}
	Y[++cnty] = W - zy.back() - 1;
	if (Y[cnty] <= 0) --cnty;

	// mark all black cells
	for (int i = 1; i <= n; ++i) mark[posx[x[i]]][posy[y[i]]] = true;

	// new board: [1...cntx][1...cnty]
	for (int i = 1; i <= cntx; ++i) {
		for (int j = 1; j <= cnty; ++j) if (!mark[i][j]) {
			bfs(i, j);
		}
	}

	cout << 1LL * ans * (int)(5e8 + 4) % mod << endl;
}