human
Give me a Python program to print the only line — the number of ways to choose the side for each coin modulo 109 + 7 = 1000000007 given the following:
Arkady and Kirill visited an exhibition of rare coins. The coins were located in a row and enumerated from left to right from 1 to k, each coin either was laid with its obverse (front) side up, or with its reverse (back) side up.

Arkady and Kirill made some photos of the coins, each photo contained a segment of neighboring coins. Akrady is interested in obverses, so on each photo made by him there is at least one coin with obverse side up. On the contrary, Kirill is interested in reverses, so on each photo made by him there is at least one coin with its reverse side up.

The photos are lost now, but Arkady and Kirill still remember the bounds of the segments of coins each photo contained. Given this information, compute the remainder of division by 109 + 7 of the number of ways to choose the upper side of each coin in such a way, that on each Arkady's photo there is at least one coin with obverse side up, and on each Kirill's photo there is at least one coin with reverse side up.

Input

The first line contains three integers k, n and m (1 ≤ k ≤ 109, 0 ≤ n, m ≤ 105) — the total number of coins, the number of photos made by Arkady, and the number of photos made by Kirill, respectively.

The next n lines contain the descriptions of Arkady's photos, one per line. Each of these lines contains two integers l and r (1 ≤ l ≤ r ≤ k), meaning that among coins from the l-th to the r-th there should be at least one with obverse side up.

The next m lines contain the descriptions of Kirill's photos, one per line. Each of these lines contains two integers l and r (1 ≤ l ≤ r ≤ k), meaning that among coins from the l-th to the r-th there should be at least one with reverse side up.

Output

Print the only line — the number of ways to choose the side for each coin modulo 109 + 7 = 1000000007.

Examples

Input

5 2 2
1 3
3 5
2 2
4 5

Output

8

Input

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

Output

0

Input

60 5 7
1 3
50 60
1 60
30 45
20 40
4 5
6 37
5 18
50 55
22 27
25 31
44 45

Output

732658600

Note

In the first example the...
#incl
assistant
#Here is Python program to print the only line — the number of ways to choose the side for each coin modulo 109 + 7 = 1000000007.
ude <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 1e5 + 5;
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
void rem(int &x, int y) {
  x -= y;
  if (x < 0) x += mod;
}
int mul(int x, int y) { return 1ll * x * y % mod; }
int fpow(int a, int p) {
  if (!p) return 1;
  int tmp = fpow(a, p >> 1);
  tmp = mul(tmp, tmp);
  if (p & 1) tmp = mul(tmp, a);
  return tmp;
}
struct Matrix {
  vector<vector<int>> a;
  int n, m;
  Matrix(int _n = 0, int _m = 0) {
    n = _n, m = _m;
    a.resize(n);
    for (int i = 0; i < n; i++) {
      a[i].resize(m);
      for (int j = 0; j < m; j++) a[i][j] = 0;
    }
  }
  Matrix operator*(const Matrix &rhs) const {
    Matrix ans = Matrix(n, rhs.m);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < rhs.m; j++) {
        ans.a[i][j] = 0;
        for (int k = 0; k < m; k++) add(ans.a[i][j], mul(a[i][k], rhs.a[k][j]));
      }
    return ans;
  }
} mulMat, mulMat2[30];
int k, n, m;
vector<int> impor;
map<int, int> endUp, endDown;
map<int, int> pSum[2];
void calc(Matrix &def, int pow) {
  for (int i = 0; i < 30; i++)
    if (pow & (1 << i)) def = def * mulMat2[i];
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> k >> n >> m;
  for (int i = 0; i < n; i++) {
    int l, r;
    cin >> l >> r;
    impor.push_back(l - 1), impor.push_back(r);
    endUp[r] = max(endUp[r], l);
  }
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    impor.push_back(l - 1), impor.push_back(r);
    endDown[r] = max(endDown[r], l);
  }
  impor.push_back(0);
  impor.push_back(k - 1);
  impor.push_back(k);
  sort(impor.begin(), impor.end());
  impor.resize(unique(impor.begin(), impor.end()) - impor.begin());
  mulMat = Matrix(4, 4);
  mulMat.a[0][0] = mulMat.a[0][1] = mulMat.a[1][0] = mulMat.a[1][1] =
      mulMat.a[2][2] = mulMat.a[3][3] = 1;
  mulMat.a[3][0] = mod - 1;
  mulMat.a[2][1] = mod - 1;
  mulMat2[0] = mulMat;
  for (int i = 1; i <...