2234: 日程 schedule.cpp

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

[丛雨]需要计划你接下来 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≤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≤109
对于再15%的数据,有1≤n≤100000,m=0,1≤k≤109

对于再10%的数据,有1≤n≤50000,1≤m≤50000,1≤k≤109

对于再10%的数据,有1≤n≤80000,1≤m≤80000,1≤k≤109

对于再40%的数据,有1≤n≤100000,1≤m≤100000,1≤k≤109
保证1≤l≤r≤k。