阿尔卡迪和基里尔参观了稀有硬币展览。硬币排成一排,从左到右从 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。