Problem: Little girl Masha likes winter sports, today she's planning to take part in slalom skiing.

The track is represented as a grid composed of n × m squares. There are rectangular obstacles at the track, composed of grid squares. Masha must get from the square (1, 1) to the square (n, m). She can move from a square to adjacent square: either to the right, or upwards. If the square is occupied by an obstacle, it is not allowed to move to that square.

One can see that each obstacle can actually be passed in two ways: either it is to the right of Masha's path, or to the left. Masha likes to try all ways to do things, so she would like to know how many ways are there to pass the track. Two ways are considered different if there is an obstacle such that it is to the right of the path in one way, and to the left of the path in the other way.

Help Masha to find the number of ways to pass the track. The number of ways can be quite big, so Masha would like to know it modulo 109 + 7.

The pictures below show different ways to pass the track in sample tests. <image> <image> <image>

Input

The first line of input data contains three positive integers: n, m and k (3 ≤ n, m ≤ 106, 0 ≤ k ≤ 105) — the size of the track and the number of obstacles.

The following k lines contain four positive integers each: x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) — coordinates of bottom left, and top right squares of the obstacle. 

It is guaranteed that there are no obstacles at squares (1, 1) and (n, m), and no obstacles overlap (but some of them may touch).

Output

Output one integer — the number of ways to pass the track modulo 109 + 7.

Examples

Input

3 3 0


Output

1


Input

4 5 1
2 2 3 4


Output

2


Input

5 5 3
2 2 2 3
4 2 5 2
4 4 4 4


Output

3

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct point {
  int x, y;
  bool can;
  bool operator<(const point &temp) const {
    if (x == temp.x) return y < temp.y;
    return x < temp.x;
  }
};
point pt[101000];
int y_list[101000], cnt_y;
struct rec {
  int lx, ly, rx, ry, flag, id;
};
rec rr[101000], sg[2][401000], tmp[2][101000], xx[201000];
int cs, dp[102000];
struct pp {
  int y, id;
  bool operator<(const pp &temp) const {
    if (y == temp.y) return id < temp.id;
    return y < temp.y;
  }
};
set<pp> hs;
set<pp>::iterator it;
pp now;
int n, m, k, cnt_sg[2], cnt;
bool cmp1(rec a, rec b) {
  if (a.lx == b.lx) {
    if (a.flag == b.flag) return a.ly < b.ly;
    return a.flag < b.flag;
  }
  return a.lx < b.lx;
}
bool cmp2(rec a, rec b) {
  if (a.ly == b.ly) return a.flag < b.flag;
  return a.ly < b.ly;
}
struct segment_tree {
  int l, r, vl, x;
};
segment_tree tree[1 << 20];
void build(int left, int right, int id) {
  int l = 2 * id + 1, r = 2 * id + 2, mid = (left + right) >> 1;
  tree[id].l = y_list[left];
  tree[id].r = y_list[right];
  tree[id].x = -1;
  tree[id].vl = 0;
  if (left == right) return;
  build(left, mid, l);
  build(mid + 1, right, r);
}
int query(int left, int right, int id) {
  int l = 2 * id + 1, r = 2 * id + 2;
  if (tree[id].r < left || tree[id].l > right) return 0;
  if (tree[id].l >= left && tree[id].r <= right) return tree[id].vl;
  return (query(left, right, l) + query(left, right, r)) % mod;
}
void insert(int pos, int vl, int id) {
  if (tree[id].l == tree[id].r) {
    if (vl > 0)
      tree[id].vl = vl;
    else
      tree[id].vl = 0;
    return;
  }
  int l = 2 * id + 1, r = 2 * id + 2;
  if (tree[l].r < pos)
    insert(pos, vl, r);
  else
    insert(pos, vl, l);
  tree[id].vl = (tree[l].vl + tree[r].vl) % mod;
}
int main() {
  int i, j, s, p, q, id;
  scanf("%d%d%d", &n, &m, &k);
  pt[cnt].x = pt[cnt].y = 0;
  cnt++;
  pt[cnt].x = n - 1;
  pt[cnt++].y = m - 1;
  for (i = 0; i < k; i++) {
    scanf("%d%d%d%d", &rr[i].lx, &rr[i].ly, &rr[i].rx, &rr[i].ry);
    rr[i].lx--;
    rr[i].ly--;
    rr[i].rx--;
    rr[i].ry--;
    if (rr[i].ry + 1 < m && rr[i].lx - 1 >= 0) {
      pt[cnt].x = rr[i].lx - 1;
      pt[cnt++].y = rr[i].ry + 1;
    }
    sg[0][cnt_sg[0]].lx = rr[i].lx;
    sg[0][cnt_sg[0]].rx = rr[i].lx;
    sg[0][cnt_sg[0]].ly = rr[i].ly;
    sg[0][cnt_sg[0]].id = i;
    sg[0][cnt_sg[0]].flag = -1;
    sg[0][cnt_sg[0]++].ry = rr[i].ry;
    sg[0][cnt_sg[0]].lx = sg[0][cnt_sg[0]].rx = rr[i].rx;
    sg[0][cnt_sg[0]].id = i;
    sg[0][cnt_sg[0]].flag = 1;
    sg[0][cnt_sg[0]].ly = rr[i].ly;
    sg[0][cnt_sg[0]++].ry = rr[i].ry;
    sg[1][cnt_sg[1]].flag = -1;
    sg[1][cnt_sg[1]].lx = rr[i].lx;
    sg[1][cnt_sg[1]].rx = rr[i].rx;
    sg[1][cnt_sg[1]].id = i;
    sg[1][cnt_sg[1]].ly = sg[1][cnt_sg[1]].ry = rr[i].ly;
    cnt_sg[1]++;
    sg[1][cnt_sg[1]].flag = 1;
    sg[1][cnt_sg[1]].id = i;
    sg[1][cnt_sg[1]].lx = rr[i].lx;
    sg[1][cnt_sg[1]].rx = rr[i].rx;
    sg[1][cnt_sg[1]].ly = sg[1][cnt_sg[1]].ry = rr[i].ry;
    cnt_sg[1]++;
  }
  for (i = 0; i < cnt; i++) {
    sg[0][cnt_sg[0]].lx = sg[0][cnt_sg[0]].rx = pt[i].x;
    sg[0][cnt_sg[0]].ly = sg[0][cnt_sg[0]].ry = pt[i].y;
    sg[0][cnt_sg[0]].id = i + cnt;
    sg[0][cnt_sg[0]++].flag = 0;
    sg[1][cnt_sg[1]++] = sg[0][cnt_sg[0] - 1];
  }
  sort(sg[0], sg[0] + cnt_sg[0], cmp1);
  sort(sg[1], sg[1] + cnt_sg[1], cmp2);
  hs.clear();
  for (i = 0; i < cnt; i++) pt[i].can = true;
  for (i = 0; i < cnt_sg[0]; i++) {
    now.id = sg[0][i].id;
    now.y = sg[0][i].ly;
    if (sg[0][i].flag < 0)
      hs.insert(now);
    else if (sg[0][i].flag > 0)
      hs.erase(now);
    else {
      id = sg[0][i].id - cnt;
      now.id = -mod;
      it = hs.lower_bound(now);
      if (it != hs.end()) {
        if (rr[it->id].ly == pt[id].y) pt[id].can = false;
      }
      tmp[1][id].lx = tmp[1][id].rx = pt[id].x;
      if (it != hs.begin()) {
        it--;
        if (rr[it->id].ry == pt[id].y) pt[id].can = false;
        tmp[1][id].ly = rr[it->id].ry + 1;
      } else
        tmp[1][id].ly = 0;
      tmp[1][id].ry = pt[id].y;
    }
  }
  hs.clear();
  for (i = 0; i < cnt_sg[1]; i++) {
    now.id = sg[1][i].id;
    now.y = sg[1][i].lx;
    if (sg[1][i].flag < 0)
      hs.insert(now);
    else if (sg[1][i].flag > 0)
      hs.erase(now);
    else {
      id = sg[1][i].id - cnt;
      now.id = -mod;
      it = hs.lower_bound(now);
      if (it != hs.end()) {
        if (rr[it->id].lx == pt[id].x) pt[id].can = false;
      }
      if (it != hs.begin()) {
        it--;
        if (rr[it->id].rx == pt[id].x) pt[id].can = false;
        it++;
      }
      if (it != hs.end()) {
        tmp[0][id].lx = pt[id].x;
        tmp[0][id].rx = rr[it->id].lx - 1;
        tmp[0][id].ly = tmp[0][id].ry = pt[id].y;
      } else {
        tmp[0][id].lx = pt[id].x;
        tmp[0][id].rx = n - 1;
        tmp[0][id].ly = tmp[0][id].ry = pt[id].y;
      }
    }
  }
  int nn = 0;
  for (i = 0; i < cnt; i++) {
    if (pt[i].can) {
      pt[nn] = pt[i];
      tmp[0][nn] = tmp[0][i];
      tmp[1][nn++] = tmp[1][i];
    }
  }
  cnt = nn;
  cs = cnt_y = 0;
  for (i = 0; i < cnt; i++) {
    xx[cs].lx = xx[cs].rx = tmp[0][i].lx;
    xx[cs].ly = xx[cs].ry = tmp[0][i].ly;
    xx[cs].id = i;
    xx[cs++].flag = -1;
    xx[cs].lx = xx[cs].rx = tmp[0][i].rx;
    xx[cs].ly = xx[cs].ry = tmp[0][i].ly;
    xx[cs].id = i;
    xx[cs++].flag = 1;
    y_list[cnt_y++] = pt[i].y;
  }
  sort(y_list, y_list + cnt_y);
  nn = 0;
  for (i = 0; i < cnt_y; i++) {
    if (nn == 0 || y_list[nn - 1] < y_list[i]) y_list[nn++] = y_list[i];
  }
  cnt_y = nn;
  build(0, cnt_y - 1, 0);
  sort(xx, xx + cs, cmp1);
  for (i = 0; i < cs;) {
    for (j = i; j < cs; j++) {
      if (!(xx[i].flag == xx[j].flag && xx[i].lx == xx[j].lx)) break;
      id = xx[j].id;
      if (xx[j].flag < 0) {
        if (pt[id].x == 0) {
          for (s = 0; s < k; s++) {
            if (rr[s].lx == 0 && rr[s].ly <= pt[id].y) break;
          }
          if (s >= k) dp[id] = 1;
        } else
          dp[id] = query(tmp[1][id].ly, tmp[1][id].ry, 0);
      }
    }
    for (s = i; s < j; s++) {
      id = xx[s].id;
      insert(xx[s].ly, -xx[s].flag * dp[id], 0);
    }
    i = j;
  }
  for (i = 0; i < cnt; i++) {
    if (pt[i].x == n - 1 && pt[i].y == m - 1) break;
  }
  printf("%d\n", dp[i]);
  return 0;
}