题目描述

小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$