E. Coins Exhibition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 following ways are possible ('O' — obverse, 'R' — reverse side):

  • OROOR,
  • ORORO,
  • ORORR,
  • RROOR,
  • RRORO,
  • RRORR,
  • ORROR,
  • ORRRO.

In the second example the information is contradictory: the second coin should have obverse and reverse sides up at the same time, that is impossible. So, the answer is 0.