配点 : 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 的得分采取最优行动。
游戏结束后,游戏的分数恰好为 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