多彩的线段II

题目描述

考虑数轴上的 $n$ 个线段，其中 $i$ -th 线段的左端点是 $l_i$ ，右端点是 $r_i$ 。你需要将每个线段涂成 $k$ 中的一种颜色，这样任何两个具有相同颜色的线段都不会重叠。

计算给线段涂色的方法数。

如果存在同时满足 $l_i \le x \le r_i$ 和 $l_j \le x \le r_j$ 的实数 $x$ ，我们就认为线段 $i$ 与线段 $j$ 重叠。

如果存在一个线段在两种着色方式中具有不同的颜色，我们就说这两个线段的着色方式是不同的。

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$ ，表示测试用例的数量。对于每个测试用例

第一行包含两个整数 $n$ 和 $k$ ( $1 \le n \le 5 \times 10^5$ , $1 \le k \le 10^9$ )，分别表示段数和颜色数。

对于下面的 $n$ 行， $i$ /-行包含两个整数 $l_i$ 和 $r_i$ 。( $1 \le l_i \le r_i \le 10^9$ )表示 $i$ /th线段的左右端点。

保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$ 。

输出格式

对于每个测试用例，输出一行包含一个整数的答案。由于答案可能很大，请输出其模数 $998244353$ 。

样例 #1

样例输入 #1

2
4 3
4 7
3 4
5 8
1 3
2 1000
100 200
300 400

样例输出 #1

24
1000000

提示

设 $c_i$ 为 $i$ - 段的颜色。

对于第一个示例测试用例，给线段着色的一种有效方法是 $c_1 = 1$ 、 $c_2 = 3$ 、 $c_3 = 3$ 和 $c_4 = 1$ 。因为 $1$ -st和 $4$ -th线段没有重叠，所以 $2$ -nd和 $3$ -rd线段也没有重叠。

然而， $c_1 = 1$ ， $c_2 = 2$ ， $c_3 = 1$ 和 $c_4 = 3$ 并不是有效的方法。因为 $1$ /st和 $3$ /rd线段相互重叠，它们不可能有相同的颜色。