AT_ajo2025_final_d The Most Boring Game

整数の組の列 $ (L_1,R_1),(L_2,R_2),\ldots,(L_N,R_N) $ が与えられます． ここで， $ L_1 \leq R_1 < L_2 \leq R_2 < \cdots < L_N \leq R_N $ が保証されます． 整数の集合 $ S $ を $ S=[L_1,R_1] \cup [L_2,R_2] \cup \cdots \cup [L_N,R_N] $ と定義します． あなたは暇つぶしのために，次のような遊びを思いつきました． - 空の黒板を用意する．そして， $ S $ に含まれるそれぞれの整数 $ v $ に対し，確率 $ 1/(v+1) $ で $ v $ を黒板に書く． これらの選択はすべて独立である． - Alice と Bob を召喚し，以下のゲームを行わせる． - Alice からはじめて交互に手番をプレイする．プレイヤーは各手番で黒板に書かれた数を一つ消す． 黒板に書かれた数がなくなったらゲーム終了である． ゲームのスコアは $ ( $ "Aliceが消した数の総和" $ - $ "Bobが消した数の総和" $ ) $ である． Alice はスコアを最大化するために，Bob は最小化するために最適に行動する． 遊びの結果，ゲームのスコアがちょうど $ K $ になる確率を $ \text{mod }{998244353} $ で求めてください． 確率 $ \text{mod }{998244353} $ の定義求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 $ \frac{P}{Q} $ で表した時、 $ Q \neq 0 \pmod{998244353} $ となることが証明できます。 よって、 $ R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 $ を満たす整数 $ R $ が一意に定まります。 この $ R $ を答えてください。

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

答えを出力せよ．

### Sample Explanation 1 ゲームのスコアがちょうど $ 1 $ になるのは黒板に $ 2,3 $ が両方書かれるときのみで，この状況になる確率は $ 1/12 $ です． ### Constraints - $ 1 \leq N \leq 8 $ - $ 1 \leq L_1 \leq R_1 < L_2 \leq R_2 < \cdots < L_N \leq R_N \leq 9 \times 10^8 $ - $ 0 \leq K \leq R_N $ - 入力はすべて整数