随机第 K 大值

题目描述

我们有 $N$ 个连续随机变量 $X_1, X_2, \dots, X_N$。$X_i$ 在区间 $[L_i, R_i]$ 上服从连续均匀分布。

设 $E$ 为这 $N$ 个随机变量中第 $K$ 大的值的期望。输出 $E \bmod {998244353}$,其含义如下。

在本题中,可以证明 $E$ 总是有理数。此外,本题的约束条件保证,当 $E$ 表示为既约分数 $\frac{y}{x}$ 时,$x$ 不被 $998244353$ 整除。

此时,存在唯一的介于 $0$ 和 $998244352$ 之间的整数 $z$,满足 $xz \equiv y \pmod{998244353}$。请输出这个 $z$,作为 $E \bmod {998244353}$ 的值。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

输出 $E \bmod {998244353}$。

样例

1 1
0 2

1

答案是区间 $[0, 2]$ 上服从连续均匀分布的随机变量的期望。因此,应输出 $1$。

2 2
0 2
1 3

707089751

答案用有理数表示是 $\frac{23}{24}$。由于 $707089751 \times 24 \equiv 23 \pmod{998244353}$,因此应输出 $707089751$。

10 5
35 48
44 64
47 59
39 97
36 37
4 91
38 82
20 84
38 50
39 69

810056397

数据范围

• $1 \le N \le 50$
• $1 \le K \le N$
• $0 \le L_i \lt R_i \le 100$
• 输入中的所有值均为整数。