### 问题描述 接下来需要计划你接下来 $k$ 天的日程。 在每一天里，你可以选择学习或者颓废，但是为了劳逸结合，日程表有两类限制： 1、在某个时间段中至少有一天要学习。 2、在某个时间段中至少有一天要颓废。 请问一共有多少种合法的日程表？答案对 $1000000007$ 取模。 ### 输入格式 第一行三个非负整数 $k$ , $n$ , $m$ ，分别表示天数，至少有一天学习的时间段个数和至少有一天颓废的时间段个数。 接下来 $n$ 行，每行两个正整数 $l$ ,$r$，表示第 $l$ 至第 $r$ 天中至少有一天学习。 接下来 $m$ 行，每行两个正整数 $l$ , $r$ ，表示第 $l$ 至第 $r$ 天中至少有一天颓废。 ### 输出格式 一行一个整数，表示答案对 $1000000007$ 取模后的结果。 ### 输入样例 ``` 5 2 2 1 3 3 5 2 2 4 5 ``` ### 输出样例 ``` 8 ``` ### 数据范围 对于 $5\%$ 的数据，有 $1 \leq n \leq 100,1 \leq m \leq 100,1 \leq k \leq 1000$ 。 对于再 $5\%$ 的数据，有 $1 \leq n \leq 1000,1 \leq m \leq 1000,1 \leq k \leq 1000$ 。 对于再 $15\%$ 的数据，有 $1 \leq n \leq 1000,1 \leq m \leq 1000,1 \leq k \leq 10^9$。 对于再 $15\%$ 的数据，有 $1 \leq n \leq 100000,m = 0,1 \leq k \leq 10^9$。 对于再 $10\%$ 的数据，有 $1 \leq n \leq 50000$ ，$1 \leq m \leq 50000,1 \leq k \leq 10^9$ 。 对于再 $10\%$ 的数据，有 $ 1 \leq n \leq 80000,1 \leq m \leq 80000,1 \leq k \leq 10^9$ 。 对于再 $40\%$ 的数据，有 $1 \leq n \leq 100000,1 \leq m \leq 100000,1 \leq k \leq 10^9$ 。 保证$1 \leq l \leq r \leq k$ 。