#T2132. 日程

日程

问题说明

小Q需要你帮忙计划接下来 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
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
732658600

数据范围

对于5%的数据,有1≤n≤100,1≤m≤100,1≤k≤1000。

对于再5%的数据,有1≤n≤1000,1≤m≤1000,1≤k≤1000。

对于再15%的数据,有1≤n≤1000,1≤m≤1000,1≤k≤10​^9^。

对于再15%的数据,有1≤n≤100000,m=0,1≤k≤10​^9​。

对于再10%的数据,有1≤n≤50000,1≤m≤50000,1≤k≤10​^9。

对于再10%的数据,有1≤n≤80000,1≤m≤80000,1≤k≤10​^9。

对于再40%的数据,有1≤n≤100000,1≤m≤100000,1≤k≤10​^9​。

保证1≤l≤r≤k。