D - The Most Boring Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1200 点

問題文

整数の組の列 (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 を答えてください。

制約

  • 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
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

N K
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

答えを出力せよ．

入力例 1

1 1
2 3

出力例 1

582309206

ゲームのスコアがちょうど 1 になるのは黒板に 2,3 が両方書かれるときのみで，この状況になる確率は 1/12 です．

入力例 2

2 3
1 2
4 6

出力例 2

443664157

入力例 3

3 0
1 1
10 10
100 100

出力例 3

230917011

入力例 4

5 78
2 3
5 8
13 21
34 55
89 144

出力例 4

495194560

入力例 5

8 608571543
17343953 20441194
126035510 225432305
226186035 246776041
310203273 364411927
468578834 469724135
489470456 504928885
639604101 708138853
771369549 852001013

出力例 5

550996549