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 <cstdio>
#include <cstring>
#include <queue>
#include <utility>

const int N = 30;
const int N2 = N * 2 + 1;
const int M = 1000000;
const int MOD = (int)1e9 + 7;
const int DELTA_X[] = {-1, 0, 0, 1};
const int DELTA_Y[] = {0, -1, 1, 0};

void update(int& x, int a)
{
    x += a;
    if (x >= MOD) {
        x -= MOD;
    }
}

int extra(int* c, int* id, int* sz, int w, int h, int n)
{
    int up = h - c[0], down = (1LL * w * h - n - up) % MOD, result = id[0] = 0;
    sz[0] = 1;
    for (int i = 1; i < w; ++ i) {
        id[i] = id[i - 1];
        if (!c[i - 1] && !c[i]) {
            update(result, 1LL * up * down % MOD);
        } else {
            id[i] ++;
        }
        sz[id[i]] ++;
        update(up, h - c[i]);
        update(down, MOD - h + c[i]);
    }
    return result;
}

int h, w, n, x[N], y[N], cx[M], cy[M], idx[M], idy[M], szx[N2], szy[N2], blk[N2][N2], dis[N2][N2];

int sz(int x, int y)
{
    return 1LL * szx[x] * szy[y] % MOD;
}

int main()
{
#ifdef LOCAL_JUDGE
    freopen("I.in", "r", stdin);
#endif
    scanf("%d%d%d", &h, &w, &n);
    for (int i = 0; i < n; ++ i) {
        scanf("%d%d", x + i, y + i);
        cx[x[i]] ++, cy[y[i]] ++;
    }
    int result = (2LL * (extra(cx, idx, szx, h, w, n) + extra(cy, idy, szy, w, h, n))) % MOD;
    for (int i = 0; i < n; ++ i) {
        blk[idx[x[i]]][idy[y[i]]] = true;
    }
    for (int sx = 0; sx <= idx[h - 1]; ++ sx) {
        for (int sy = 0; sy <= idy[w - 1]; ++ sy) {
            if (!blk[sx][sy]) {
                memset(dis, -1, sizeof(dis));
                dis[sx][sy] = 0;
                std::queue<std::pair<int, int>> q;
                q.emplace(sx, sy);
                while (!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    update(result, 1LL * sz(sx, sy) * sz(x, y) % MOD * dis[x][y] % MOD);
                    for (int k = 0; k < 4; ++ k) {
                        int xx = x + DELTA_X[k];
                        int yy = y + DELTA_Y[k];
                        if (0 <= xx && xx <= idx[h - 1] && 0 <= yy && yy <= idy[w - 1] && !blk[xx][yy] && !~dis[xx][yy]) {
                            dis[xx][yy] = dis[x][y] + 1;
                            q.emplace(xx, yy);
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", static_cast<int>(500000004LL * result % MOD));
}
