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 <algorithm>
#include <vector>
#include <queue>

const int MOD = (int)1e9 + 7;
const int inv2 = MOD + 1 >> 1;
const int kN = 30;
const int kM = kN * 2 + 5;
int h, w, n, x[kN], y[kN];
std::vector<int> sx, sy;
int mat[kM][kM];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};

inline void add(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}

int main()
{
    scanf("%d%d%d", &h, &w, &n);
    sx.emplace_back(-1);
    sx.emplace_back(h);
    sy.emplace_back(-1);
    sy.emplace_back(w);
    for (int i = 0; i < n; ++ i) {
        scanf("%d%d", x + i, y + i);
        sx.emplace_back(x[i]);
        sy.emplace_back(y[i]);
    }
    auto prepare = [](std::vector<int> &v) {
        std::sort(v.begin(), v.end());
        v.erase(std::unique(v.begin(), v.end()), v.end());
        std::vector<int> w;
        for (int i = 0; i < v.size(); ++ i) {
            if (w.empty() || w.back() != v[i]) w.emplace_back(v[i]);
            if (i + 1 < v.size()) w.emplace_back(v[i] + 1);
        }
        w.swap(v);
    };
    auto get = [](const std::vector<int> &v, int x) {
        return std::lower_bound(v.begin(), v.end(), x) - v.begin();
    };
    prepare(sx);
    prepare(sy);
    for (int i = 0; i < n; ++ i) {
        mat[get(sx, x[i])][get(sy, y[i])] = 1;
    }
    int result = 0;
    auto calcEmpty = [&result](const std::vector<int> &sx, int w, int h, int* x, int n) {
        for (int i = 1; i + 1 < sx.size(); ++ i) if (sx[i + 1] - sx[i] > 1) {
            int t = sx[i + 1] - sx[i];
            int up = sx[i] * 1LL * w % MOD;
            int down = (h - sx[i + 1]) * 1LL * w % MOD;
            for (int j = 0; j < n; ++ j) {
                if (x[j] < sx[i]) add(up, MOD - 1);
                else add(down, MOD - 1);
            }
            // printf("t = %d, up = %d, down = %d\n", t, up, down);
            // printf("sx[i] = %d, sx[i + 1] = %d\n", sx[i], sx[i + 1]);
            for (int j = 1; j < t; ++ j)
                add(result, (up + j * 1LL * w) % MOD * 1LL * ((down + (t - j) * 1LL * w) % MOD) % MOD);
        }
    };
    calcEmpty(sx, w, h, x, n);
    // printf("%d\n", result);
    calcEmpty(sy, h, w, y, n);
    // printf("%d\n", result);
    // for (int i = 0; i < sx.size(); ++ i)
    //     for (int j = 0; j < sy.size(); ++ j)
    //         printf("%d%c", mat[i][j], " \n"[j + 1 == sy.size()]);
    for (int i = 1; i + 1 < sx.size(); ++ i) {
        for (int j = 1; j + 1 < sy.size(); ++ j) if (mat[i][j] == 0) {
            std::vector<std::vector<int>> dist(sx.size(), std::vector<int>(sy.size(), -1));
            dist[i][j] = 0;
            std::queue<int> que;
            que.emplace(i);
            que.emplace(j);
            while (!que.empty()) {
                int x = que.front(); que.pop();
                int y = que.front(); que.pop();
                for (int d = 0; d < 4; ++ d) {
                    int tx = x + dir[d][0];
                    int ty = y + dir[d][1];
                    if (tx <= 0 || tx + 1 >= sx.size() || ty <= 0 || ty + 1 >= sy.size() || mat[tx][ty] || dist[tx][ty] != -1) continue;
                    dist[tx][ty] = dist[x][y] + 1;
                    que.emplace(tx);
                    que.emplace(ty);
                }
            }
            for (int ii = 1; ii + 1 < sx.size(); ++ ii)
                for (int jj = 1; jj + 1 < sy.size(); ++ jj) 
                    if (dist[ii][jj] > 0) {
                        add(result, dist[ii][jj] * 1LL * (sx[i + 1] - sx[i]) % MOD * (sy[j + 1] - sy[j]) % MOD *
                            (sx[ii + 1] - sx[ii]) % MOD * (sy[jj + 1] - sy[jj]) % MOD * inv2 % MOD);
                        // printf("i = %d, j = %d, ii = %d, jj = %d\n", i, j, ii, jj);
                    }
        }
    }
    printf("%d\n", result);
}
