English · Original
Chinese · Translation
Formal · Original
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.
[samples]
## 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.
Arkady 和 Kirill 参观了一个稀有硬币展览。硬币排成一行，从左到右编号为 #cf_span[1] 到 #cf_span[k]，每个硬币要么正面朝上，要么反面朝上。
Arkady 和 Kirill 对硬币拍摄了一些照片，每张照片包含一段相邻的硬币。Arkady 对正面感兴趣，因此他拍摄的每张照片中至少有一枚正面朝上的硬币。相反，Kirill 对反面感兴趣，因此他拍摄的每张照片中至少有一枚反面朝上的硬币。
现在照片丢失了，但 Arkady 和 Kirill 仍然记得每张照片所包含硬币段的边界。给定这些信息，请计算满足以下条件的硬币朝向方案数对 #cf_span[109 + 7] 取模的结果：每张 Arkady 的照片中至少有一枚正面朝上的硬币，且每张 Kirill 的照片中至少有一枚反面朝上的硬币。
第一行包含三个整数 #cf_span[k]、#cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ k ≤ 109]，#cf_span[0 ≤ n, m ≤ 105]）——硬币总数、Arkady 拍摄的照片数和 Kirill 拍摄的照片数。
接下来的 #cf_span[n] 行描述 Arkady 的照片，每行一个。每行包含两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ l ≤ r ≤ k]），表示在第 #cf_span[l] 枚到第 #cf_span[r] 枚硬币中，至少有一枚正面朝上。
接下来的 #cf_span[m] 行描述 Kirill 的照片，每行一个。每行包含两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ l ≤ r ≤ k]），表示在第 #cf_span[l] 枚到第 #cf_span[r] 枚硬币中，至少有一枚反面朝上。
请输出一行——满足条件的硬币朝向方案数对 #cf_span[109 + 7 = 1000000007] 取模的结果。
在第一个例子中，以下方案是可能的（'_O_' 表示正面，'_R_' 表示反面）：
在第二个例子中，信息矛盾：第二枚硬币必须同时正面和反面朝上，这是不可能的。因此答案为 #cf_span[0]。
## Input
第一行包含三个整数 #cf_span[k]、#cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ k ≤ 109]，#cf_span[0 ≤ n, m ≤ 105]）——硬币总数、Arkady 拍摄的照片数和 Kirill 拍摄的照片数。接下来的 #cf_span[n] 行描述 Arkady 的照片，每行一个。每行包含两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ l ≤ r ≤ k]），表示在第 #cf_span[l] 枚到第 #cf_span[r] 枚硬币中，至少有一枚正面朝上。接下来的 #cf_span[m] 行描述 Kirill 的照片，每行一个。每行包含两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ l ≤ r ≤ k]），表示在第 #cf_span[l] 枚到第 #cf_span[r] 枚硬币中，至少有一枚反面朝上。
## Output
请输出一行——满足条件的硬币朝向方案数对 #cf_span[109 + 7 = 1000000007] 取模的结果。
[samples]
## Note
在第一个例子中，以下方案是可能的（'_O_' 表示正面，'_R_' 表示反面）：_OROOR_、_ORORO_、_ORORR_、_RROOR_、_RRORO_、_RRORR_、_ORROR_、_ORRRO_。在第二个例子中，信息矛盾：第二枚硬币必须同时正面和反面朝上，这是不可能的。因此答案为 #cf_span[0]。
Let $ k $ be the number of coins, indexed from $ 1 $ to $ k $. Each coin $ i $ has a state $ x_i \in \{0,1\} $, where $ x_i = 1 $ denotes obverse (O), and $ x_i = 0 $ denotes reverse (R).
Let $ A = \{(l_j, r_j)\}_{j=1}^n $ be the set of Arkady’s intervals: for each $ (l, r) \in A $, we require
$$
\bigvee_{i=l}^r x_i = 1
$$
Let $ K = \{(l_j, r_j)\}_{j=1}^m $ be the set of Kirill’s intervals: for each $ (l, r) \in K $, we require
$$
\bigvee_{i=l}^r (1 - x_i) = 1 \quad \iff \quad \bigwedge_{i=l}^r x_i = 0 \text{ is false} \quad \iff \quad \exists i \in [l, r] \text{ s.t. } x_i = 0
$$
We are to compute the number of assignments $ (x_1, \dots, x_k) \in \{0,1\}^k $ satisfying **all** constraints from $ A $ and $ K $, modulo $ 10^9 + 7 $.
---
### Formal Statement:
Define the set of valid assignments:
$$
\mathcal{S} = \left\{ (x_1, \dots, x_k) \in \{0,1\}^k \;\middle|\;
\begin{array}{c}
\forall (l,r) \in A,\; \exists i \in [l,r] \text{ such that } x_i = 1 \\
\forall (l,r) \in K,\; \exists i \in [l,r] \text{ such that } x_i = 0
\end{array}
\right\}
$$
Compute:
$$
|\mathcal{S}| \mod (10^9 + 7)
$$
---
### Additional Notes (for implementation context, not part of formal output):
- The constraints may be contradictory (e.g., a coin must be both 0 and 1), in which case $ |\mathcal{S}| = 0 $.
- $ k $ can be up to $ 10^9 $, but $ n, m \leq 10^5 $, so we must use coordinate compression and interval analysis.
- The problem reduces to counting binary sequences satisfying union-of-interval constraints: at least one 1 in each Arkady interval, at least one 0 in each Kirill interval.
- This is a classical constraint satisfaction problem over binary sequences with interval constraints, solvable via inclusion-exclusion or dynamic programming over compressed coordinates, but the **formal mathematical statement** is as above.
API Response (JSON)
{
"problem": {
"name": "G. Coins Exhibition",
"description": {
"content": "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 w",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF944G"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 w...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Arkady 和 Kirill 参观了一个稀有硬币展览。硬币排成一行，从左到右编号为 #cf_span[1] 到 #cf_span[k]，每个硬币要么正面朝上，要么反面朝上。\n\nArkady 和 Kirill 对硬币拍摄了一些照片，每张照片包含一段相邻的硬币。Arkady 对正面感兴趣，因此他拍摄的每张照片中至少有一枚正面朝上的硬币。相反，Kirill 对反面感兴趣，因此他拍摄的每张照片中至少有一...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ k $ be the number of coins, indexed from $ 1 $ to $ k $. Each coin $ i $ has a state $ x_i \\in \\{0,1\\} $, where $ x_i = 1 $ denotes obverse (O), and $ x_i = 0 $ denotes reverse (R).\n\nLet $ A = \\...",
"is_translate": false,
"language": "Formal"
}
]
}