题目描述

一个集合内含有若干个闭区间，定义这个集合的价值为集合内所有区间的并形成的连通块的数目的 K 次方(K 是给出的一个定值)。

例如当 K=3 时，集合 $\{[1,3], [2,4], [5,6]\}$ 的价值为 $2^3=8$.

现在给出数轴上的 $N$ 个闭区间 $[L_i, R_i]$ ，求 $N$ 个闭区间的所有子集（共有 $2^N$ 个）的价值之和。答案可能很大，你只需要输出其 $mod$ $(10^9+7)$ 的值。

输入格式

第一行：两个整数 $N, K$。(1≤N≤10^5, 2≤K≤10)

接下来 $N$ 行，每行两个整数 $L_i,R_i$，描述一个区间。保证 $1 ≤ L_i < R_i ≤ 2N$，且任意两个区间的端点不重合。

输出格式

一个整数，表示答案 $mod$ $(10^9+7)$

样例输入

3 2
1 6
2 3
4 5

样例输出

10

数据范围

测试点 1∼2 满足 N≤16；

测试点 3∼5 满足 N≤10^3，且 K=2；

测试点 6∼8 满足 N≤10^3；

对于测试点 T（T∈[9,16]），满足 K=3+(T−9)。