[AdditionalFile3267.zip](file://AdditionalFile3267.zip?type=additional_file)

#3267. 「USACO 2020.2 Platinum」Help Yourself

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

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

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

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

Bessie 现在想计算这 $N$ 条线段的 $2^N$ 个子集的复杂度之和模 $10^9+7$。通常你的任务是帮 Bessie 进行计算，但是这次你是 Bessie，而且没人能帮你，帮帮你自己吧！

输入格式

第一行两个空格分隔的整数 $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]\}\rightarrow1$

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

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

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

数据范围与提示

测试点 $2$ 满足 $N\le 16$。

测试点 $3\ldots 5$ 满足 $N\le 1000,~K=2$。

测试点 $6-8$ 满足 $N\le 1000$。

测试点 $T\in [9,~16]$ 满足 $K=3+(T-9)$。

对于 $100\%$ 的数据，有 $1\le N \le 10^5,~2\le K\le 10,~1\le l_i<r_i\le 2N$。