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 <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long i64;
const i64 MOD = 1000000007;
void ADD(i64& a, const i64& b) { a = (a + b) % MOD; }

i64 H, W;
int N, X[30], Y[30];
int hist[1001001];

i64 precomp(i64 H, i64 W, int *Y)
{
    for (int i = 0; i < H; ++i) hist[i] = 0;
    for (int i = 0; i < N; ++i) hist[Y[i]]++;

    i64 tot = (H * W - N) % MOD;
    i64 suml = 0;
    i64 ret = 0;
    for (int i = 1; i < H; ++i) {
        ADD(suml, W - hist[i - 1]);
        i64 sumr = (MOD + tot - suml) % MOD;
        if (hist[i - 1] == 0 && hist[i] == 0) {
            ADD(ret, suml * sumr);
        }
    }
    return ret;
}
vector<pair<int, int>> summarize(int H, int *Y)
{
    vector<int> ys;
    for (int i = 0; i < N; ++i) ys.push_back(Y[i]);
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    
    vector<pair<int, int>> ret;
    if (ys[0] != 0) ret.push_back({0, ys[0] - 1});
    ret.push_back({ys[0], ys[0]});
    for (int i = 1; i < ys.size(); ++i) {
        if (ys[i - 1] < ys[i] - 1) ret.push_back({ys[i - 1] + 1, ys[i] - 1});
        ret.push_back({ys[i], ys[i]});
    }
    if (ys.back() != H - 1) ret.push_back({ys.back() + 1, H - 1});
    return ret;
}

int R, C; i64 weight[90][90];
int dis[90][90];

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};

i64 bfs(int y, int x)
{
    for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) dis[i][j] = -1;
    dis[y][x] = 0;
    queue<pair<int, int>> qu; qu.push({y, x});
    i64 ret = 0;
    while (!qu.empty()) {
        auto loc = qu.front(); qu.pop();
        int d = dis[loc.first][loc.second];
        if (make_pair(y, x) < make_pair(loc.first, loc.second)) {
            ADD(ret, d * weight[loc.first][loc.second]);
        }
        for (int i = 0; i < 4; ++i) {
            int y2 = loc.first + dy[i], x2 = loc.second + dx[i];
            if (y2 < 0 || x2 < 0 || y2 >= R || x2 >= C || weight[y2][x2] == 0 || dis[y2][x2] != -1) continue;
            dis[y2][x2] = d + 1;
            qu.push({y2, x2});
        }
    }
    return ret;
}

int main()
{
    scanf("%lld%lld%d", &H, &W, &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d%d", Y + i, X + i);
    }

    i64 ret = 0;
    ADD(ret, precomp(H, W, Y));
    ADD(ret, precomp(W, H, X));

    vector<pair<int, int>> ys = summarize(H, Y), xs = summarize(W, X);
    R = ys.size(); C = xs.size();
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            weight[i][j] = (i64)(ys[i].second - ys[i].first + 1) * (xs[j].second - xs[j].first + 1);
        }
    }
    for (int i = 0; i < N; ++i) {
        int u = find(ys.begin(), ys.end(), make_pair(Y[i], Y[i])) - ys.begin();
        --weight[find(ys.begin(), ys.end(), make_pair(Y[i], Y[i])) - ys.begin()][find(xs.begin(), xs.end(), make_pair(X[i], X[i])) - xs.begin()];
    }
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (weight[i][j] != 0) {
                ADD(ret, weight[i][j] % MOD * bfs(i, j));
            }
        }
    }
    printf("%lld\n", ret);

    return 0;
}
