说明

需要计划你接下来 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

提示

输入样例2

<o:p></o:p>

60 5 7<o:p></o:p>

1 3<o:p></o:p>

50 60<o:p></o:p>

1 60<o:p></o:p>

30 45<o:p></o:p>

20 40<o:p></o:p>

4 5<o:p></o:p>

6 37<o:p></o:p>

5 18<o:p></o:p>

50 55<o:p></o:p>

22 27<o:p></o:p>

25 31<o:p></o:p>

44 45<o:p></o:p>

输出样例2<o:p></o:p>

732658600<o:p></o:p>

数据范围<o:p></o:p>

对于5%的数据，有1≤n≤100，1≤m≤100，1≤k≤1000。<o:p></o:p>

对于再5%的数据，有1≤n≤1000，1≤m≤1000，1≤k≤1000。<o:p></o:p>

对于再15%的数据，有1≤n≤1000，1≤m≤1000，1≤k≤10⁹。<o:p></o:p>

对于再15%的数据，有1≤n≤100000，m=0，1≤k≤10⁹。<o:p></o:p>

对于再10%的数据，有1≤n≤50000，1≤m≤50000，1≤k≤10⁹。<o:p></o:p>

对于再10%的数据，有1≤n≤80000，1≤m≤80000，1≤k≤10⁹。<o:p></o:p>

对于再40%的数据，有1≤n≤100000，1≤m≤100000，1≤k≤10⁹。<o:p></o:p>

保证1≤l≤r≤k。<o:p></o:p>

注：本题测试时间为2s