Coins Exhibition

题意翻译

### 题目大意 有$k(1 \leq k \leq 10^9)$个硬币，每个硬币有正面朝上和反面朝上两种状态。 现有$n+m(0 \leq n,m \leq 10^5)$个限制条件，每个限制条件形如$(l_i,r_i)(1 \leq l_i \leq r_i \leq k)$。前$n$个限制条件限制区间$[l_i,r_i]$内至少有一个硬币正面朝上，后$m$个限制条件限制区间$[l_i,r_i]$内至少有一个硬币反面朝上。 问共有多少种摆放硬币的方案使得所有限制条件都被满足。答案对$10^9+7$取模。 ### 输入数据格式 第一行三个整数$k,n,m$ 接下来$n+m$行每行两个正整数$l_i,r_i$表示一个限制区间 ### 输出数据格式 一行表示方案数

题目描述

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 $ 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.

输入输出格式

输入格式

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.

输出格式

Print the only line — the number of ways to choose the side for each coin modulo $ 10^{9}+7=1000000007 $ .

输入输出样例

输入样例 #1

5 2 2
1 3
3 5
2 2
4 5

输出样例 #1

8

输入样例 #2

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

输出样例 #2

0

输入样例 #3

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

输出样例 #3

732658600

说明

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 $ .