#P18187. Many Common Segment Problems

Many Common Segment Problems

Many Common Segment Problems

PCT 编写了下面这道题。

Common Segment

给定 NN 个区间 [L1,R1],…,[LN,RN][L_1,R_1],\ldots,[L_N,R_N]。这里 [L,R][L,R] 表示从 LL 到 RR 的所有整数,包括端点。

从这 NN 个区间中选择一个或多个,共有 2N−12^N-1 种选择。求所选区间的公共部分非空的选择数,答案对 998244353998244353 取模。

Many Common Segment Testcases

PCT 不小心丢失了一份 Common Segment 测试数据中的部分 Li,RiL_i,R_i。丢失的数被替换成了 −1-1。

已知原数据满足 1≤Li≤Ri≤M1\le L_i\le R_i\le M。请对所有可能的原测试数据分别求解 Common Segment,再把这些答案相加,对 998244353998244353 取模后输出。

不同的原数据由各下标的区间端点共同确定。即使两个区间的端点完全相同,它们仍是下标不同的两个区间。只替换 −1-1,保留其他已知端点。

输入格式

第一行两个整数 N,MN,M。

接下来 NN 行,第 ii 行两个整数 Li,RiL_i,R_i,表示第 ii 个区间已知或丢失的端点。

输出格式

输出一个整数,表示所有可能原测试数据答案的总和,模 998244353998244353。

数据范围

  • 1≤N,M≤1051\le N,M\le10^5;
  • Li=−1L_i=-1 或 1≤Li≤M1\le L_i\le M;
  • Ri=−1R_i=-1 或 1≤Ri≤M1\le R_i\le M;
  • 如果两个端点都已知,则 Li≤RiL_i\le R_i;
  • 所有输入均为整数。

样例 1

输入

3 3
1 -1
2 2
2 3

输出

18

第一个区间可以补全为 [1,1][1,1]、[1,2][1,2] 或 [1,3][1,3]。对应三个原实例的答案分别为 4,7,74,7,7,所以总和为 1818。

样例 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