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 std::pair;
using std::vector;
using std::string;

typedef long long ll;
typedef pair<int, int> pii;

#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)

template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int oo = 0x3f3f3f3f;

string procStatus() {
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}

template <typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x *= f;
}

const int P = 100;
const int N = 1000000;
const int mo = 1e9 + 7;

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

int n, ans;
int cx[N + 5], cy[N + 5];
int ix[N + 5], iy[N + 5];
int sx[N + 5], sy[N + 5], totX, totY;

inline int size(int x, int y) {
    return 1ll * sx[x] * sy[y] % mo;
}

int solve(int *cnt, int *id, int *s, int R, int C) {
    int l = R - cnt[0], r = (1ll * R * C - n - l) % mo;

    ++ s[0];
    for(int i = 1; i < C; ++i) {
        id[i] = id[i-1];

        if(!cnt[i] && !cnt[i-1]) {
            ans = (ans + 1ll * l * r) % mo;
        } else {
            ++ id[i];
        }
        ++ s[id[i]];
        l = (l + R - cnt[i]) % mo;
        r = (r + cnt[i] - R) % mo;
    }
    return id[C - 1] + 1;
}

int r, c;
int dis[P + 5][P + 5];
bool vis[P + 5][P + 5];
int x[P + 5], y[P + 5];

int main() {
#ifdef Wearry
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    read(r), read(c), read(n);
    for(int i = 0; i < n; ++i) {
        read(x[i]), read(y[i]);
        ++ cx[x[i]], ++ cy[y[i]];
    }

    totY = solve(cy, iy, sy, r, c);
    totX = solve(cx, ix, sx, c, r);

    ans = ans * 2 % mo;
    for(int i = 0; i < n; ++i) vis[ix[x[i]]][iy[y[i]]] = true;
    for(int i = 0; i < totX; ++i) 
        for(int j = 0; j < totY; ++j) if(!vis[i][j]) {
            std::queue<pii> q;
            memset(dis, 0xff, sizeof dis);

            dis[i][j] = 0;
            q.push(mp(i, j));

            while(!q.empty()) {
                pii cur = q.front(); q.pop();

                ans = (ans + 1ll * dis[cur.fst][cur.snd] * size(cur.fst, cur.snd) % mo * size(i, j)) % mo;

                for(int d = 0; d < 4; ++ d) {
                    pii nxt = mp(cur.fst + dx[d], cur.snd + dy[d]);

                    if(nxt.fst >= 0 && nxt.fst < totX &&!~dis[nxt.fst][nxt.snd]
                    && nxt.snd >= 0 && nxt.snd < totY && !vis[nxt.fst][nxt.snd]) {
                        dis[nxt.fst][nxt.snd] = dis[cur.fst][cur.snd] + 1;
                        q.push(nxt);
                    }
                }
            }
        }

    printf("%lld\n", 1ll * ans * (mo + 1) / 2 % mo);

    return 0;
}
