样例下载

题目描述

在一个数轴上有 $N$ 条线段，第 $i$ 条线段覆盖了从 $l_i$ 到 $r_i$ 的所有实数（包含 $l_i$ 和 $r_i$）。

定义若干条线段的并为一个包含了所有被至少一个线段覆盖的点的集合。

定义若干条线段的复杂度为这些线段的并形成的连通块的数目的 $K$ 次方。

现在要求出给定 $N$ 条线段的所有子集（共有 $2^N$ 个）的复杂度之和对 $10^9+7$ 取模的结果。

输入格式

第一行两个整数 $N$，$K$。

接下来 $N$ 行，每行两个整数 $l_i,r_i$，描述一条线段。保证 $1 ≤ l_i < r_i ≤ 2N$，且任意两个端点都不在同一位置上。

输出格式

输出所求答案对 $10^9+7$ 取模的结果。

输入样例

3 2
1 6
2 3
4 5

输出样例

10

样例解释

所有非空子集的复杂度如下所示（显然空集的复杂度为零）：

$ \{[1,6]\} \implies 1, \{[2,3]\} \implies 1, \{[4,5]\} \implies 1 $

$ \{[1,6],[2,3]\} \implies 1, \{[1,6],[4,5]\} \implies 1, \{[2,3],[4,5]\} \implies 4 $

$\{[1,6],[2,3],[4,5]\} \implies 1$

故答案为 $1+1+1+1+1+4+1=10$。

数据范围

满分 100 分，共 28 个测试点，全部满足 $1 ≤ N ≤ 10^5$, $1 ≤ K ≤ 10$。具体地：

30分：

• 测试点 $1 - 3$ 满足 $N ≤ 16$, $K=1$；
• 测试点 $4 - 7$ 满足 $N ≤ 10^3$, $K=1$；
• 测试点 $8 - 12$ 满足 $N ≤ 10^5$, $K=1$；

30分：

• 测试点 $13 - 14$ 满足 $N ≤ 16$, $K=2$；
• 测试点 $15 - 17$ 满足 $N ≤ 10^3$, $K=2$；
• 测试点 $18 - 20$ 满足 $N ≤ 10^3$, $1 ≤ K ≤ 10$。

40分：

• 测试点 $21 - 28$ 满足 $N ≤ 10^5$, $1 ≤ K ≤ 10$。