← 返回题目列表

Codeforces · 930/E

E. 钱币展览

中文机器翻译题面 查看原题

阿尔卡迪和基里尔参观了稀有硬币展览。硬币排成一排,从左到右从 1 到 k 依次排列,每枚硬币要么正面朝上,要么反面朝上。

Arkady 和 Kirill 拍摄了一些硬币的照片,每张照片都包含一段相邻的硬币。 Akrady 对正面很感兴趣,因此在他拍摄的每张照片上,至少有一枚硬币正面朝上。相反,基里尔对反面很感兴趣,所以在他拍摄的每张照片上,至少有一枚硬币的反面朝上。

照片现在已经丢失,但阿尔卡迪和基里尔仍然记得每张照片所包含的硬币片段的范围。给定此信息,计算除以 109 + 7 的余数,以选择每枚硬币正面的方式数,使得在每张 Arkady 的照片上至少有一枚硬币正面朝上,在每张 Kirill 的照片上至少有一枚硬币反面朝上。

输入

第一行包含三个整数 k、n 和 m(1 ≤ k ≤ 109、0 ≤ n、m ≤ 105)——分别是硬币总数、Arkady 拍摄的照片数量和 Kirill 拍摄的照片数量。

接下来的n行包含Arkady照片的描述,每行一个。每行包含两个整数 l 和 r (1 ≤ l ≤ r ≤ k),这意味着从第 l 到第 r 枚硬币中至少应该有一枚正面朝上。

接下来的 m 行包含基里尔照片的描述,每行一个。每行包含两个整数 l 和 r (1 ≤ l ≤ r ≤ k),这意味着从第 l 到第 r 的硬币中至少应该有一个反面朝上。

输出

打印唯一一行 — 每个硬币选择面的方式数模 109 + 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

注意

在第一个示例中,可以采用以下方式(“O”— 正面,“R”— 反面):

- 奥罗尔,
- 奥罗罗,
- 奥罗尔,
- RROOR,
- 罗罗,
- RRRRRR,
- 错误,
- 奥罗。

在第二个例子中,信息是矛盾的:第二枚硬币的正面和反面应该同时朝上,这是不可能的。所以,答案是0。