#P18187. Many Common Segment Problems
Many Common Segment Problems
Many Common Segment Problems
PCT 编写了下面这道题。
Common Segment
给定 个区间 。这里 表示从 到 的所有整数,包括端点。
从这 个区间中选择一个或多个,共有 种选择。求所选区间的公共部分非空的选择数,答案对 取模。
Many Common Segment Testcases
PCT 不小心丢失了一份 Common Segment 测试数据中的部分 。丢失的数被替换成了 。
已知原数据满足 。请对所有可能的原测试数据分别求解 Common Segment,再把这些答案相加,对 取模后输出。
不同的原数据由各下标的区间端点共同确定。即使两个区间的端点完全相同,它们仍是下标不同的两个区间。只替换 ,保留其他已知端点。
输入格式
第一行两个整数 。
接下来 行,第 行两个整数 ,表示第 个区间已知或丢失的端点。
输出格式
输出一个整数,表示所有可能原测试数据答案的总和,模 。
数据范围
- ;
- 或 ;
- 或 ;
- 如果两个端点都已知,则 ;
- 所有输入均为整数。
样例 1
输入
3 3
1 -1
2 2
2 3
输出
18
第一个区间可以补全为 、 或 。对应三个原实例的答案分别为 ,所以总和为 。
样例 2
输入
5 8
1 7
2 3
4 8
6 8
1 5
输出
15
样例 3
输入
10 13
4 -1
-1 -1
7 11
-1 -1
-1 -1
-1 -1
11 -1
3 8
-1 9
-1 -1
输出
841024210