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 <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long lint;

const int mod = 1e9 + 7, inv6 = (mod + 1) / 6;

struct edge_t {
  int u, dist;
};

int sum_x(int n) {
  return (lint)n * (n + 1) / 2 % mod;
}

int sum_x2(int n) {
  return (lint)n * (2 * n + 1) % mod * (n + 1) % mod * inv6 % mod;
}

int all_to_corner(int small, int big) {
  if (small > big) return all_to_corner(big, small);
  const int max_dist = (small - 1) + (big - 1);
  int result = (lint)max_dist * sum_x(small - 1) % mod;
  result =
    (result + (lint)(sum_x(big - 1) - sum_x(small - 2)) * small) % mod;
  if (result < 0) result += mod;
  return result;
}

int solve_self_one_coord(int r, int c) {
  int result = 0;
  int sum_a = ((lint)c * sum_x(c) - sum_x2(c)) % mod;
  if (sum_a < 0) sum_a += mod;
  result = (result + (lint)r * (r - 1) % mod * sum_a) % mod;
  result = (result + (lint)r * sum_a) % mod;
  return result;
}

int solve_self(int h, int w) {
  int result = solve_self_one_coord(h, w) + solve_self_one_coord(w, h);
  if (result >= mod) result -= mod;
  return result;
}

int solve_by_corner(int dist, int h1, int w1, int h2, int w2) {
  int s1 = (lint)h1 * w1 % mod, s2 = (lint)h2 * w2 % mod;
  int result = (lint)dist * s1 % mod * s2 % mod;
  result = (result + (lint)all_to_corner(h1, w1) * s2) % mod;
  result = (result + (lint)all_to_corner(h2, w2) * s1) % mod;
  return result;
}

int unit_to_corner(int h, int w, int dist) {
  int result = all_to_corner(h, w);
  result = (result + (lint)h * w % mod * dist) % mod;
  return result;
}

int solve_unit_to_rectangle(int h, int w, int d0, int d1, int d2, int d3) {
  int div_y = (d2 - d0 + h - 1) / 2;
  int div_x = (d1 - d0 + w - 1) / 2;
  int result = unit_to_corner(div_y + 1, div_x + 1, d0);
  if (div_y + 1 < h) {
    result += unit_to_corner(h - (div_y + 1), div_x + 1, d2);
    if (result >= mod) result -= mod;
  }
  if (div_x + 1 < w) {
    result += unit_to_corner(div_y + 1, w - (div_x + 1), d1);
    if (result >= mod) result -= mod;
  }
  if (div_y + 1 < h && div_x + 1 < w) {
    result += unit_to_corner(h - (div_y + 1), w - (div_x + 1), d3);
    if (result >= mod) result -= mod;
  }
  return result;
}

int solve_greedy_same_row(int r, int c1, int c2, int dist) {
  int sum_a = ((lint)r * sum_x(r) - sum_x2(r)) % mod;
  if (sum_a < 0) sum_a += mod;
  int result = 2LL * c1 * c2 % mod * sum_a % mod;
  result = (result + (lint)r * r % mod * c2 % mod * sum_x(c1 - 1)) % mod;
  result = (result + (lint)r * r % mod * c1 % mod * sum_x(c2 - 1)) % mod;
  result = (result + (lint)r * r % mod * c1 % mod * c2 % mod * dist) % mod;
  return result;
}

void dijkstra(const vector<vector<edge_t>> &adj, int source,
              vector<int> &min_dist) {
  const int n = adj.size();
  fill(min_dist.begin(), min_dist.end(), INT_MAX);
  //  assert(min_dist.size() == n);
  static priority_queue<pair<int, int>, vector<pair<int, int>>,
                        greater<pair<int, int>>> pq;
  min_dist[source] = 0;
  pq.emplace(min_dist[source], source);
  while (!pq.empty()) {
    pair<int, int> dist_and_v = pq.top(); pq.pop();
    int dist_v, v;
    tie(dist_v, v) = dist_and_v;
    if (dist_v != min_dist[v]) continue;
    for (const edge_t &ed : adj[v])
      if (min_dist[ed.u] > min_dist[v] + ed.dist) {
        min_dist[ed.u] = min_dist[v] + ed.dist;
        pq.emplace(min_dist[ed.u], ed.u);
      }
  }
  //  for (int i = 0; i < n; ++i)
  //    assert(min_dist[i] < INT_MAX);
}

int main() {
  int height, width;
  scanf("%d %d", &height, &width);
  int nblack;
  scanf("%d", &nblack);
  vector<pair<int, int>> blacks(nblack);
  for (int i = 0; i < nblack; ++i) {
    int y, x;
    scanf("%d %d", &y, &x);
    blacks[i] = {y, x};
  }
  vector<int> ys = {0, height}, xs = {0, width};
  for (int i = 0; i < nblack; ++i) {
    ys.push_back(blacks[i].first);
    ys.push_back(blacks[i].first + 1);
    xs.push_back(blacks[i].second);
    xs.push_back(blacks[i].second + 1);
  }
  sort(ys.begin(), ys.end());
  ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
  sort(xs.begin(), xs.end());
  xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
  const int ny = ys.size() - 1, nx = xs.size() - 1;
  vector<bool> row_has_black(ny), col_has_black(nx);
  vector<vector<bool>> is_black(ny, vector<bool>(nx, false));
  for (int i = 0; i < nblack; ++i) {
    int y = lower_bound(ys.begin(), ys.end(), blacks[i].first) - ys.begin();
    int x = lower_bound(xs.begin(), xs.end(), blacks[i].second) - xs.begin();
    row_has_black[y] = true;
    col_has_black[x] = true;
    is_black[y][x] = true;
  }
  vector<vector<edge_t>> adj;
  vector<vector<array<int, 4>>> corner_id(ny, vector<array<int, 4>>(nx));
  auto new_node = [&]() {
    int result = adj.size();
    adj.emplace_back();
    return result;
  };
  auto add_edge = [&](int u, int v, int dist) {
    adj[u].push_back({v, dist});
    adj[v].push_back({u, dist});
  };
  for (int y = 0; y < ny; ++y)
    for (int x = 0; x < nx; ++x)
      if (!is_black[y][x]) {
        const int cell_height = ys[y + 1] - ys[y];
        const int cell_width = xs[x + 1] - xs[x];
        corner_id[y][x][0] = new_node();
        if (cell_width == 1) {
          corner_id[y][x][1] = corner_id[y][x][0];
        } else {
          corner_id[y][x][1] = new_node();
          add_edge(corner_id[y][x][1], corner_id[y][x][0], cell_width - 1);
        }
        if (cell_height == 1) {
          corner_id[y][x][2] = corner_id[y][x][0];
          corner_id[y][x][3] = corner_id[y][x][1];
        } else {
          corner_id[y][x][2] = new_node();
          add_edge(corner_id[y][x][2], corner_id[y][x][0], cell_height - 1);
          if (cell_width == 1) {
            corner_id[y][x][3] = corner_id[y][x][2];
          } else {
            corner_id[y][x][3] = new_node();
            add_edge(corner_id[y][x][3], corner_id[y][x][2], cell_width - 1);
            add_edge(corner_id[y][x][3], corner_id[y][x][1], cell_height - 1);
          }
        }

        if (y - 1 >= 0 && !is_black[y - 1][x]) {
          add_edge(corner_id[y][x][0], corner_id[y - 1][x][2], 1);
          if (cell_width > 1) {
            add_edge(corner_id[y][x][1], corner_id[y - 1][x][3], 1);
          }
        }
        if (x - 1 >= 0 && !is_black[y][x - 1]) {
          add_edge(corner_id[y][x][0], corner_id[y][x - 1][1], 1);
          if (cell_height > 1) {
            add_edge(corner_id[y][x][2], corner_id[y][x - 1][3], 1);
          }
        }
      }
  vector<int> dists(adj.size());
  int result = 0;
  for (int y = 0; y < ny; ++y)
    for (int x = 0; x < nx; ++x)
      if (!is_black[y][x]) {
        const int cell_height = ys[y + 1] - ys[y];
        const int cell_width = xs[x + 1] - xs[x];
        result += solve_self(cell_height, cell_width);
        if (result >= mod) result -= mod;

        if (row_has_black[y] && col_has_black[x]) {
          dijkstra(adj, corner_id[y][x][0], dists);
          for (int y2 = 0; y2 < ny; ++y2)
            for (int x2 = 0; x2 < nx; ++x2)
              if (!is_black[y2][x2] &&
                  (!(row_has_black[y2] && col_has_black[x2]) ||
                   make_pair(y, x) < make_pair(y2, x2))) {
                result += solve_unit_to_rectangle(
                    ys[y2 + 1] - ys[y2], xs[x2 + 1] - xs[x2],
                    dists[corner_id[y2][x2][0]], dists[corner_id[y2][x2][1]],
                    dists[corner_id[y2][x2][2]], dists[corner_id[y2][x2][3]]);
                if (result >= mod) result -= mod;
              }
        } else {
          bool computed_dists = false;
          for (int y2 = y; y2 < ny; ++y2)
            for (int x2 = 0; x2 < nx; ++x2)
              if (!is_black[y2][x2] && make_pair(y2, x2) > make_pair(y, x) &&
                  !(row_has_black[y2] && col_has_black[x2])) {
                if (row_has_black[y] && row_has_black[y2] && x != x2) {
                  if (computed_dists == false) {
                    dijkstra(adj, corner_id[y][x][0], dists);
                    computed_dists = true;
                  }
                  int min_dist;
                  if (x2 > x) {
                    min_dist = dists[corner_id[y2][x2][0]] - (cell_width - 1);
                  } else {
                    min_dist = dists[corner_id[y2][x2][1]];
                  }
                  result += solve_by_corner(min_dist, 1, xs[x + 1] - xs[x],
                                            1, xs[x2 + 1] - xs[x2]);
                  if (result >= mod) result -= mod;
                } else if (col_has_black[x] && col_has_black[x2] && y != y2) {
                  if (computed_dists == false) {
                    dijkstra(adj, corner_id[y][x][0], dists);
                    computed_dists = true;
                  }
                  int min_dist;
                  if (y2 > y) {
                    min_dist = dists[corner_id[y2][x2][0]] - (cell_height - 1);
                  } else {
                    min_dist = dists[corner_id[y2][x2][2]];
                  }
                  result += solve_by_corner(min_dist, 1, ys[y + 1] - ys[y],
                                            1, ys[y2 + 1] - ys[y2]);
                  if (result >= mod) result -= mod;
                } else if (y == y2) {
                  int min_dist;
                  if (x2 > x) min_dist = xs[x2] - xs[x + 1] + 1;
                  else min_dist = xs[x] - xs[x2 + 1] + 1;
                  result += solve_greedy_same_row(ys[y + 1] - ys[y],
                                                  xs[x + 1] - xs[x],
                                                  xs[x2 + 1] - xs[x2],
                                                  min_dist);
                  if (result >= mod) result -= mod;
                } else if (x == x2) {
                  int min_dist;
                  if (y2 > y) min_dist = ys[y2] - ys[y + 1] + 1;
                  else min_dist = ys[y] - ys[y2 + 1] + 1;
                  result += solve_greedy_same_row(xs[x + 1] - xs[x],
                                                  ys[y + 1] - ys[y],
                                                  ys[y2 + 1] - ys[y2],
                                                  min_dist);
                  if (result >= mod) result -= mod;
                } else {
                  int min_dist = 0;
                  if (y2 > y) min_dist += ys[y2] - ys[y + 1] + 1;
                  else min_dist += ys[y] - ys[y2 + 1] + 1;
                  if (x2 > x) min_dist += xs[x2] - xs[x + 1] + 1;
                  else min_dist += xs[x] - xs[x2 + 1] + 1;
                  result += solve_by_corner(min_dist,
                                            ys[y + 1] - ys[y],
                                            xs[x + 1] - xs[x],
                                            ys[y2 + 1] - ys[y2],
                                            xs[x2 + 1] - xs[x2]);
                  if (result >= mod) result -= mod;
                }
              }
        }
      }
  printf("%d\n", result);
  return 0;
}
