Problem Statement

We have $N$ continuous random variables $X_1,X_2,\dots,X_N$. $X_i$ has a continuous uniform distribution over the interval $\lbrack L_i, R_i \rbrack$. Let $E$ be the expected value of the $K$-th greatest value among the $N$ random variables. Print $E \bmod {998244353}$ as specified in Notes.

Note

In this problem, we can prove that $E$ is always a rational number. Additionally, the Constraints of this problem guarantee that, when $E$ is represented as an irreducible fraction $\frac{y}{x}$, $x$ is indivisible by $998244353$. Here, there uniquely exists an integer $z$ between $0$ and $998244352$ such that $xz \equiv y \pmod{998244353}$. Print this $z$ as the value $E \bmod {998244353}$.

Constraints

• $1 \leq N \leq 50$
• $1 \leq K \leq N$
• $0 \leq L_i \lt R_i \leq 100$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

Print $E \bmod {998244353}$.