P14239 [CCPC 2024 Shandong I] 多彩的线段 2

考虑数轴上的 $n$ 条线段，其中第 $i$ 条线段的左端点为 $l_i$，右端点为 $r_i$。您需要将每条线段涂上 $k$ 种颜色中的一种，使得任意两条具有相同颜色的线段都没有重合。 求给线段涂色的方案数。 称第 $i$ 条线段和第 $j$ 条线段有重合，若存在一个实数 $x$ 同时满足 $l_i \le x \le r_i$ 且 $l_j \le x \le r_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$ 条线段的左右端点。 保证所有数据 $n$ 之和不超过 $5 \times 10^5$。

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

令 $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$ 条线段互相重合，不能有一样的颜色。