問題文

PCT 君は以下のような問題を作りました。

Common Segment

N 個の区間 [L_1,R_1],[L_2,R_2],\dots,[L_N,R_N] が与えられます。ここで [L, R] は L 以上 R 以下の全ての整数からなる区間を意味します。

ここから 1 個以上の区間を選ぶ方法は 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

部分点

この問題には複数の部分点が設定されている。

• L_i,R_i \ge 1 を満たすデータセットに正解した場合 10 点が与えられる。
• N,M \le 2000 を満たすデータセットに正解した場合 10 点が与えられる。

入力例 1

3 3
1 -1
2 2
2 3

出力例 1

18

テストケースとしてあり得るもの全てとそのテストケースに対する 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 となります。

入力例 2

5 8
1 7
2 3
4 8
6 8
1 5

出力例 2

15

入力例 3

10 13
4 -1
-1 -1
7 11
-1 -1
-1 -1
-1 -1
11 -1
3 8
-1 9
-1 -1

出力例 3

841024210