题目描述
小M有 $n$ 个取值为$\textbf{实数}$的变量 $x_1,x_2,..,x_n$,由于小M不喜欢确定的事情,所以 $x_i$ 的值在 $[l_i,r_i)$ 之间均匀随机。
现在小M 想要知道 $\lfloor{x_1+x_2+...+x_n}\rfloor^k$ 的期望取值是多少。可以证明是有理数,你只需要输出对 $998244353$ 取模之后的值。
输入格式
第一行两个整数 $n,k$
接下来 $n$ 行,每行两个整数表示 $l_i,r_i$
输出格式
输出一个数,表示你的答案。
样例 #1
样例输入 #1
2 2
1 2
3 5
样例输出 #1
499122202
样例解释:
$\lfloor x_1+x_2\rfloor$ 取到 $4$ 的概率为 $1\over 4$,取到 $5$ 的概率为 $1\over 2$,取到 $6$ 的概率为 $1\over 4$,所以$E[\lfloor{x_1+x_2}\rfloor^2]={1\over 4} \times (4^2+6^2)+{1\over 2}\times 5^2={51\over 2}$
样例 #2
样例输入 #2
10 10
192 204
114 514
191 981
214 336
123 456
789 921
721 888
323 452
193 844
321 443
样例输出 #2
740425590
提示
对于 $100\%$ 的数据,$n\le 10^3,k\le 20,0\le l_i < r_i<998244352$
对于前$10\%$ 的数据,$n=2,k=1$
对于前 $20\%$ 的数据,$n\le 10,r_i-l_i\le 5$
对于另外 $10\%$ 的数据, $k=1$
对于前 $50\%$ 的数据,$r_i-l_i\le 10$
对于前 $70\%$ 的数据,$k\le 3$
对于另外 $10\%$ 的数据,$l_i=0,r_i=1$