問題文

牛丼店「ゆき家」には $K$ 種類の料理があります。

この店に客が $N$ 人来店します。客 $i$ は時刻 $L_i$ に来店し、時刻 $R_i-0.1$ に退店します。どの客も料理を $1$ つだけ注文します。

$N$ 人の客の注文の仕方は $K^N$ 通りありますが、このうちある時刻において同じ料理を注文している $2$ 人が同時に店内に存在するようなものは何通りありますか。

答えを $998244353$ で割った余りを求めてください。

制約

• $1\le N\le 10^5$
• $1\le K\le 10^9$
• $1\le L_i\lt R_i\le 2\times 10^5$
• 入力はすべて整数

入力

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

出力

条件を満たす注文の仕方が何通りあるかを求め、$998244353$ で割った余りを出力してください。

サンプル

3 2
1 4
3 5
5 8

4

5 1
31 32
41 42
59 60
26 27
53 54

0

5 4
1 10
2 9
3 8
4 7
5 6

1024