You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题说明

小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。