考虑数轴上的 条线段，其中第 条线段的左端点为 ，右端点为 。您需要将每条线段涂上 种颜色中的一种，使得任意两条具有相同颜色的线段都没有重合。
求给线段涂色的方案数。
称第 条线段和第 条线段有重合，若存在一个实数 同时满足 且 。
称两种涂色方案是不同的，若存在一条线段在两种方案中被涂上了不同的颜色。
有多组测试数据。第一行输入一个整数 表示测试数据组数。对于每组测试数据：
第一行输入两个整数 和 （，）表示线段的数量和颜色的数量。
对于接下来的 行，第 行输入两个整数 和 （）表示第 条线段的左右端点。
保证所有数据 之和不超过 。
每组数据输出一行一个整数表示答案。由于答案可能很大，请将答案对 取模后输出。
2 4 3 4 7 3 4 5 8 1 3 2 1000 100 200 300 400
24 1000000
令 表示第 条线段的颜色。
对于第一组样例数据，一种合法的涂色方案是令 ，， 以及 。因为第 条和第 条线段没有重合，第 条和第 条线段也没有重合。
然而， ，， 以及 不是一种合法的方案。因为第 条和第 条线段互相重合，不能有一样的颜色。
