好的，我们重新整理题目，并在公式和数字前后加上 $。

题目描述

题目译自 USACO 2020 February Contest, Platinum Problem 3. Help Yourself

Bessie 现在有 $N$ 条在一条数轴上的线段，第 $i$ 条线段覆盖了 $[l_i, r_i]$ 的所有实数。

定义一个线段集合的并为所有至少被一条线段覆盖的实数。
定义一个线段集合的复杂度为该集合并的连通块个数的 $K$ 次方。

Bessie 现在想计算这 $N$ 条线段的所有 $2^N$ 个子集的复杂度之和，结果对 $10^9+7$ 取模。

输入格式

第一行两个空格分隔的整数 $N$, $K$。

接下来 $N$ 行，每行两个空格分隔的整数 $l_i$, $r_i$。

输出格式

输出所求的值模 $10^9+7$。

样例

输入

3 2
1 6
2 3
4 5

输出

10

解释
各个非空子集的复杂度如下：

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

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

数据范围与提示

• $1 \le N \le 10^5$
• $2 \le K \le 10$
• $1 \le l_i < r_i \le 2N$

测试点 2 满足 $N \le 16$。
测试点 3~5 满足 $N \le 1000$, $K = 2$。
测试点 6~8 满足 $N \le 1000$。
测试点 9~16 满足 $K = 3 + (T - 9)$，其中 $T$ 是测试点编号。