You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

限制

• 时间限制：$2s$
• 空间限制：$256M$

题目描述

考虑数轴上的$n$条线段，其中第$i$条线段的左端点为$l_i$，右端点为$r_i$。您需要将每条线段涂上$k$种颜色 中的一种，使得任意两条具有相同颜色的线段都没有重合。 求给线段涂色的方案数。 称第$i$条线段和第 $j$ 条线段有重合，若存在一个实数$x$同时满足 $l_i \le x \le r_i$ 且$l_j \le x \le r_j$。 称两种涂色方案是不同的，若存在一条线段在两种方案中被涂上了不同的颜色。

输入格式

第一行输入两个整数$n$和$k$ $（1 \le n \le 5*10^5，1 \le k \le 10^9）$表示线段的数量和颜色的数量。 对于接下来的$n$行，第i行输入两个整数$l_i$和$r_i$$（1 \le l_i \lt r_i \le 10^9）$表示第$i$条线段的左右端点。

输出格式

每组数据输出一行一个整数表示答案。由于答案可能很大，请将答案对 $998244353$ 取模后输出。

样例

输入

4 3
4 7
3 4
5 8
1 3

输出

24

样例解释

令$c_i$ 表示第$i$条线段的颜色。 对于第一组样例数据，一种合法的涂色方案是令$c_1=1$，$c_2=3$，$c_3=3$以及$c_4=1$。因为第$1$条和第$4$ 条线段没有重合，第$2$条和第$3$条线段也没有重合。 然而，$c_1=1，c_2 =2，c_3 =1$ 以及 $c_4 =3$ 不是一种合法的方案。因为第$1$条和第$3$条线段互相重合， 不能有一样的颜色

数据分布

$40\%$ 的样例，$（1 \le n \le 100，1 \le k \le 1000）$ ，左右区间端点$l_i$和$r_i$$（1 \le l_i \lt r_i \le 1000）$

$100\%$的样例，$（1 \le n \le 5*10^5，1 \le k \le 10^9）$ ，左右区间端点$l_i$和$r_i$ $（1 \le l_i \lt r_i \le 10^9）$