Consider $$$n$$$ segments on the number axis, where the left endpoint of the $$$i$$$-th segment is $$$l_i$$$ and the right endpoint is $$$r_i$$$. You need to paint each segment into one of the $$$k$$$ colors, so that for any two segments with the same color they do not overlap.
Calculate the number of ways to color the segments.
We say segment $$$i$$$ overlaps with segment $$$j$$$, if there exists a real number $$$x$$$ satisfying both $$$l_i \le x \le r_i$$$ and $$$l_j \le x \le r_j$$$.
We say two ways of coloring the segments are different, if there exists one segment which has different colors in the two ways.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 5 \times 10^5$$$, $$$1 \le k \le 10^9$$$) indicating the number of segments and the number of colors.
For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$) indicating the left and right endpoints of the $$$i$$$-th segment.
It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$5 \times 10^5$$$.
For each test case output one line containing one integer indicating the answer. As the answer might be large, output it modulo $$$998244353$$$.
24 34 73 45 81 32 1000100 200300 400
24 1000000
Let $$$c_i$$$ be the color of the $$$i$$$-th segment.
For the first sample test case, one valid way to color the segments is $$$c_1 = 1$$$, $$$c_2 = 3$$$, $$$c_3 = 3$$$, and $$$c_4 = 1$$$. Because the $$$1$$$-st and the $$$4$$$-th segments do not overlap, also the $$$2$$$-nd and the $$$3$$$-rd segments do not overlap.
However, $$$c_1 = 1$$$, $$$c_2 = 2$$$, $$$c_3 = 1$$$, and $$$c_4 = 3$$$ is not a valid way. Because the $$$1$$$-st and the $$$3$$$-rd segments overlap with each other and they can't have the same color.
