Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Coins Exhibition

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputArkady 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 10^{9} + 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* ≤ 10^{9}, 0 ≤ *n*, *m* ≤ 10^{5}) — 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 10^{9} + 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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 18:38:36 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|