硬币展览

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有 $k$ 枚硬币排成一行，从左到右编号为 $1$ 到 $k$。每枚硬币恰有正面或反面朝上两种状态。

Arkady 拍摄了 $n$ 张照片。每张照片覆盖一个连续区间，并且这个区间中至少有一枚硬币正面朝上。

Kirill 拍摄了 $m$ 张照片。每张照片也覆盖一个连续区间，并且这个区间中至少有一枚硬币反面朝上。

已知所有照片覆盖的区间，求有多少种硬币朝向方案满足全部要求。答案对 $10^9+7$ 取模。

输入格式

第一行包含三个整数 $k,n,m$。

接下来 $n$ 行，每行两个整数 $l,r$，表示 Arkady 的一张照片覆盖区间 $[l,r]$，该区间内至少有一枚硬币正面朝上。

接下来 $m$ 行，每行两个整数 $l,r$，表示 Kirill 的一张照片覆盖区间 $[l,r]$，该区间内至少有一枚硬币反面朝上。

输出格式

输出一个整数，表示合法方案数对 $10^9+7$ 取模的结果。

样例输入 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

数据范围

对于全部数据，$1\le k\le 10^9$，$0\le n,m\le 10^5$，$1\le l\le r\le k$。