CF930E Coins Exhibition

Arkady 和 Kirill 参观了一个稀有硬币展览。硬币排成一排，从左到右编号为 $1$ 到 $k$，每枚硬币要么正面朝上，要么反面朝上。 Arkady 和 Kirill 拍摄了一些硬币的照片，每张照片包含一段连续的硬币。Arkady 对正面感兴趣，所以他拍摄的每张照片中至少有一枚硬币正面朝上。相反，Kirill 对反面感兴趣，所以他拍摄的每张照片中至少有一枚硬币反面朝上。 这些照片现在已经丢失，但 Arkady 和 Kirill 仍然记得每张照片所包含的硬币区间。给定这些信息，计算有多少种方式可以选择每枚硬币的朝向，使得每张 Arkady 的照片中至少有一枚硬币正面朝上，并且每张 Kirill 的照片中至少有一枚硬币反面朝上。答案对 $10^9+7$ 取模。

第一行包含三个整数 $k$、$n$ 和 $m$（$1 \leq k \leq 10^9$，$0 \leq n, m \leq 10^5$），分别表示硬币总数、Arkady 拍摄的照片数量和 Kirill 拍摄的照片数量。 接下来的 $n$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq k$），表示 Arkady 的一张照片覆盖的硬币区间，从第 $l$ 枚到第 $r$ 枚，要求该区间内至少有一枚硬币正面朝上。 接下来的 $m$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq k$），表示 Kirill 的一张照片覆盖的硬币区间，从第 $l$ 枚到第 $r$ 枚，要求该区间内至少有一枚硬币反面朝上。

输出一行，表示满足条件的硬币朝向方案数，对 $10^9+7=1000000007$ 取模。

在第一个样例中，可能的方案如下（‘O’ 表示正面，‘R’ 表示反面）： - OROOR， - ORORO， - ORORR， - RROOR， - RRORO， - RRORR， - ORROR， - ORRRO。 在第二个样例中，条件矛盾：第二枚硬币要求同时正面和反面朝上，这是不可能的。因此答案为 $0$。 由 ChatGPT 4.1 翻译