问题描述

我们有 $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$ 整除。
这里，一定存在一个整数 $z$，使得 $xz \equiv y \pmod{998244353}$，且 $z$ 介于 $0$ 和 $998244352$ 之间。将 $z$ 作为 $E \bmod {998244353}$ 的值打印出来。

约束条件

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

输入

输入以以下格式从标准输入给出：

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

输出

打印 $E \bmod {998244353}$。

示例输入 1

1 1
0 2

示例输出 1

1

答案是随机变量在区间 $[0, 2]$ 上服从均匀分布的期望值。因此，我们应该打印 $1$。

示例输入 2

2 2
0 2
1 3

示例输出 2

707089751

答案表示为一个有理数是 $\frac{23}{24}$。我们有 $707089751 \times 24 \equiv 23 \pmod{998244353}$，因此我们应该打印 $707089751$。

示例输入 3

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

示例输出 3

810056397