問題文

$N$ 個の連続確率変数 $X_1,X_2,\\dots,X_N$ があり、 $X_i$ は $\\lbrack L_i, R_i \\rbrack$ の範囲を取る連続一様分布に従います。
$N$ 個の確率変数のうち大きい方から $K$ 番目の値の期待値を $E$ とします。注記に述べるように $E \\bmod {998244353}$ を出力してください。

注記

この問題で $E$ は必ず有理数になることが証明できます。また、この問題の制約下では、$E$ を既約分数 $\\frac{y}{x}$ で表したときに $x$ が $998244353$ で割り切れないことが保証されます。
このとき $xz \\equiv y \\pmod{998244353}$ を満たすような $0$ 以上 $998244352$ 以下の整数 $z$ が一意に定まります。この $z$ を $E \\bmod {998244353}$ として出力してください。

制約

• $1 \\leq N \\leq 50$
• $1 \\leq K \\leq N$
• $0 \\leq L_i \\lt 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

$\\lbrack 0, 2 \\rbrack$ 上の連続一様分布に従う確率変数の値の期待値が求める答えです。よって $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