P3542.第3题-区间
题目内容
对于给定的n个长度相同的区间，第i个区间的左端点为li，
右端点为ri，且全部区间的长度ri−li+1固定。
你需要从中任选若干个不同的区间，使得:
- 选定的区间两两不存在交集;
- 其余区间均至少与一个选定的区间存在交集。
一共有多少种不同的选择方案?由于答案可能很大，请将答案对998 244 353取模后输出。
[名词解释]
交集: 我们定义两个闭区间[l1,r1]和[l2,r2]存在交集，当且仅当 max(l1,l2)≦min(r1,r2)。换言之，仅在端点处重合也视为存在交集。
输入描述
第一行输入一个整数n(2≦n≦105)代表区间的数量。
此后n 行，第i行输入两个整数li和ri(1≦li≦ri≦2×109)代表第i个区间的左端点和右端点。
保证所有区间的长度相同。
输出描述
输出一个整数，代表一共有多少种不同的选择方案。由于答案可能很大，请将答案对998 244 353取模后输出。
样例1
输入
3
1 3
2 4
3 5
输出
3
说明
在这个样例中，一共有三种不同的选择方案:
- 单单选择第1个区间;
- 单单选择第2个区间;
- 单单选择第3个区间。
样例2
输入
3
1 2
3 4
5 6
输出
1
说明
在这个样例中，唯一的选择方案是同时选择全部区间。
样例3
输入
7
10 13
1 4
9 12
5 8
4 7
7 10
8 11
输出
7
