AT_npcapc_2024_g Many Common Segment Problems

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 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

答えを出力せよ。

### 部分点 この問題には複数の部分点が設定されている。 - $ L_i,R_i \ge 1 $ を満たすデータセットに正解した場合 $ 10 $ 点が与えられる。 - $ N,M \le 2000 $ を満たすデータセットに正解した場合 $ 10 $ 点が与えられる。 ### Sample Explanation 1 テストケースとしてあり得るもの全てとそのテストケースに対する **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 $ となります。 ### Constraints - $ 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 $