Help Yourself

题目描述:

Bessie 得到了一条一维数轴上的 N 条线段（1≤N≤10⁵）。第 i 条线段包含满足 li≤x≤ri 的所有实数 x。

定义一组线段的并为所有被至少一条线段所包含的实数 x 的集合。定义一组线段的复杂度为这组线段的并的连通区域数量的 K 次方（2≤K≤10）。

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

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

测试点性质：

• 测试点 2 满足 N≤16。
• 测试点 3-5 满足 N≤1000, K=2。
• 测试点 6-8 满足 N≤1000。
• 对于 T∈[9,16]，测试点 T 满足 K=3+(T−9)。

输入格式:

第一行包含 N 和 K。

以下 N 行每行包含两个整数 li 和 ri。保证 li<ri，且所有 li,ri 均为 1…2N 中的不同整数。

输出格式:

输出答案模 10⁹+7 的值。

样例输入:

3 2
1 6
2 3
4 5

样例输出:

10

提示:

所有非空子集的复杂度如下。

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

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2020 FEB Platinum