PCT 提出了以下问题。

Common Segment

给定 $N$ 个区间 $[L_1, R_1], [L_2, R_2], \dots, [L_N, R_N]$。其中 $[L, R]$ 表示从 $L$ 到 $R$（包含 $L$ 和 $R$）的所有整数集合。 共有 $2^N - 1$ 种选择一个或多个区间的方法，在这些方法中，找出所有选定区间的交集非空的方案数。将结果对 $998244353$ 取模。

PCT 在测试用例中不慎丢失了一些 $L_i$ 和 $R_i$ 的值。为了帮助他，请解决以下问题。

Many Common Segment Testcases

给定 Common Segment 的测试用例。缺失的 $L_i, R_i$ 值被替换为 ‘-1’。 已知原始测试用例满足 $1 \le L_i \le R_i \le M$ ($1 \le i \le N$)。对于所有可能的原始测试用例，求解 Common Segment 并求出所有答案之和，结果对 $998244353$ 取模。

数据范围

• $1 \le N, M \le 10^5$
• $L_i = -1$ 或 $1 \le L_i \le M$
• $R_i = -1$ 或 $1 \le R_i \le M$
• 若 $L_i, R_i \ge 1$，则 $L_i \le R_i$

输入格式

输入通过标准输入按以下格式给出：

$N \ M$ $L_1 \ R_1$ $L_2 \ R_2$ $\vdots$ $L_N \ R_N$

输出格式

输出答案。

样例

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

说明

对于第一个样例： 所有可能的原始测试用例及其对应的 Common Segment 答案如下：

• 当 $(L_i, R_i) = (1, 1), (2, 2), (2, 3)$ 时，答案为 $4$。
• 当 $(L_i, R_i) = (1, 2), (2, 2), (2, 3)$ 时，答案为 $7$。
• 当 $(L_i, R_i) = (1, 3), (2, 2), (2, 3)$ 时，答案为 $7$。

因此，总答案为 $4 + 7 + 7 = 18$。