Problem 3. Help Yourself

USACO 2020 February Contest, Platinum

Bessie 得到了一条一维数轴上的 $N$ 条线段（$1\le N\le 10^5$）。第 $i$ 条线段包含满足 $l_i\le x\le r_i$ 的所有实数 $x$。

定义一组线段的

并

为所有被至少一条线段所包含的实数 $x$ 的集合。定义一组线段的

复杂度

为这组线段的并的连通区域数量的 $K$ 次方（$2\le K\le 10$）。

Bessie 想要求出给定的 $N$ 条线段组成的集合的所有 $2^N$ 个子集的复杂度之和模 $10^9+7$ 的值。

通常你的任务是帮助 Bessie。然而这次，你就是 Bessie，没人来帮你。请吧！

测试点性质： 测试点 2 满足 $N\le 16$。测试点 3-5 满足 $N\le 1000$, $K=2$。测试点 6-8 满足 $N\le 1000$。对于 $T\in [9,16]$，测试点 $T$ 满足 $K=3+(T-9)$。

输入格式（文件名：help.in）：

第一行包含 $N$ 和 $K$。

以下 $N$ 行每行包含两个整数 $l_i$ 和 $r_i$。保证 $l_i< r_i$，且所有 $l_i,r_i$ 均为 $1 \ldots 2N$ 中的不同整数。

输出格式（文件名：help.out）：

输出答案模 $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$。

供题：Benjamin Qi