[USACO20FEB] Help Yourself P

题目描述

在一个数轴上有 $N$ 条线段,第 $i$ 条线段覆盖了从 $l_i$ 到 $r_i$ 的所有实数(包含 $l_i$ 和 $r_i$)。 定义若干条线段的**并**为一个包含了所有被至少一个线段覆盖的点的集合。 定义若干条线段的**复杂度**为这些线段的并形成的连通块的数目的 $K$ 次方。 现在 Bessie 想要求出给定 $N$ 条线段的所有子集(共有 $2^N$ 个)的复杂度之和对 $10^9+7$ 取模的结果。 你也许猜到了,你需要帮 Bessie 解决这个问题。但不幸的是,你猜错了!在这道题中你就是 Bessie,而且没有人来帮助你。一切就靠你自己了!

输入输出格式

输入格式


第一行两个整数 $N$,$K$($1 \leq N \leq 10^5$。$2 \leq K \leq 10$)。 接下来 $N$ 行,每行两个整数 $l_i,r_i$,描述一条线段。保证 $1 \leq l_i \lt r_i \leq 2N$,且任意两个端点都不在同一位置上。

输出格式


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

输入输出样例

输入样例 #1

3 2
1 6
2 3
4 5

输出样例 #1

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$。 ### 子任务 - 测试点 $2$ 满足 $N \leq 16$; - 测试点 $3 \sim 5$ 满足 $N \leq 10^3$,且 $K=2$; - 测试点 $6 \sim 8$ 满足 $N \leq 10^3$; - 对于测试点 $T$($T \in [9,16]$),满足 $K=3+(T-9)$。