首先考虑 (k = 1) 的情况。
发现每条线段对前后的答案都有影响，所以按左端点排序，从左到右处理。
记 (f_i) 表示以 (i) 为结尾的线段集合的答案，最终答案即为 (sum_{i=1}^{2n} f_i) 。
对于每条加进来的线段 (egin{bmatrix}l,rend{bmatrix}) 对于不同 (f_i) 的贡献进行分类讨论。
- 对于所有 (i < l) ，此时加入这条线段后，对 (f_r) 的贡献即为 (f_i + 1) ，可以表达为 (f_r gets f_r + sum_{i=1}^{l-1} f_i+1) 。
- 对于所有 (iin[l,r]) ，加入线段后，复杂度不变，所以对 (f_r) 的贡献即为 (f_i) ，可以表达为 (f_r gets f_r + sum_{i=l}^{r} f_i)。
- 对于所有 (i > r) ，因为按照左端点排序，所以加入线段后，复杂度不变，所以 (f_i) 对 (f_i) 的贡献即为 (f_i) ，可以表达为 (f_i gets f_i imes 2)
可以直接前缀和或者线段树维护。
考虑 (k > 1)
发现棘手的地方在于维护第一种情况出现的 (sum_{i=1}^{l-1} (f_i+1)^k) 。
这里有两种解决方案。
方案一:
根据二项式定理 ((f_i+1)^k = sum_{j=0}^{k} {k choose j} f_i^j) 。
因为 (kleq 10) ，直接用线段树维护每个指数所对应的值即可。
方案二:
大力拆式子。
设 (g_s) 表示 (k=1) 时线段集合 (s) 的答案，发现最终答案可以表达为 (sum_s g_s^k) 。
直接套路次幂拆第二类斯特林数，得到：
[sum_s sum_{i=0}^{k} egin{Bmatrix}k\iend{Bmatrix} i! {g_s choose i}
]
换一下求和顺序，得：
[sum_{i=0}^k egin{Bmatrix}k\iend{Bmatrix} i! sum_s {g_s choose i}
]
设 (S_i) 表示以第 (i) 个节点结束的线段集合的集合，维护对象改为对于每一个 (j) ，求:
[f_{i,j} = displaystyle{sum_{sin S_i} {g_s choose j}}
]
再看一下上面的讨论，发现后两种针对总体贡献，直接翻倍相加即可。
问题变为如何处理 (displaystyle{{g_schoose j} ightarrow {g_s+1 choose j}}) 。
根据加法恒等式发现有转移：
[{g_s + 1 choose j} gets {g_s choose j} + {g_s choose j-1}
]
可以用线段树维护每个 (f_{i,j}) ，发现转移后面的东西已经都维护好了，直接转移即可，具体表达 (f_{i,j} gets f_{i,j} + f_{i,j-1}) 。
时间复杂度 (mathcal{O}(nklog n + nk))
Code(C++):
#include <bits/stdc++.h>
#define forn(i,s,t) for(register int i=(s);i<=(t);++i)
using namespace std;
typedef long long LL;
const int N = 1e5 + 3, M = 4e5 + 1e2, Mod = 1e9 + 7;
template<typename T>inline void redn(T &ret) {
static char ch;
ret = 0, ch = getchar();
while (!isdigit(ch))
ch = getchar();
while (isdigit(ch))
ret = (ret << 1) + (ret << 3) + ch - 48, ch = getchar();
}
int k;
LL wgt[11], trans[11];
class SegTree {
private:
int L[M], R[M], sl;
LL val[M][11], tag[M];
inline void push_up(int p) {
forn(i, 0, k) val[p][i] = val[L[p]][i] + val[R[p]][i], val[p][i] %= Mod;
}
inline void Opt(int p, LL value) {
forn(i, 0, k) val[p][i] = val[p][i] * value % Mod;
tag[p] = tag[p] * value % Mod;
}
inline void push_down(int p) {
Opt(L[p], tag[p]), Opt(R[p], tag[p]);
tag[p] = 1ll;
}
public:
int rt;
void Bld(int &p, int l, int r) {
p = ++sl, tag[p] = 1;
if (l == r)
return ;
int mid = l + r >> 1;
Bld(L[p], l, mid), Bld(R[p], mid + 1, r);
push_up(p);
}
void Qry(int p, int l, int r, int nl, int nr) {
if (l == nl && nr == r) {
forn(i, 0, k) wgt[i] = wgt[i] + val[p][i], wgt[i] %= Mod;
return ;
}
(tag[p] ^ 1) &&(push_down(p), 0);
int mid = nl + nr >> 1;
if (r <= mid)
Qry(L[p], l, r, nl, mid);
else if (l > mid)
Qry(R[p], l, r, mid + 1, nr);
else
Qry(L[p], l, mid, nl, mid), Qry(R[p], mid + 1, r, mid + 1, nr);
}
void Upd(int p, int l, int r, int pos) {
if (l == r) {
forn(i, 0, k) val[p][i] = val[p][i] + trans[i], val[p][i] %= Mod;
return ;
}
(tag[p] ^ 1) &&(push_down(p), 0);
int mid = l + r >> 1;
if (pos <= mid)
Upd(L[p], l, mid, pos);
else
Upd(R[p], mid + 1, r, pos);
push_up(p);
}
void Mul(int p, int l, int r, int nl, int nr) {
if (l == nl && nr == r)
return Opt(p, 2ll);
(tag[p] ^ 1) &&(push_down(p), 0);
int mid = nl + nr >> 1;
if (r <= mid)
Mul(L[p], l, r, nl, mid);
else if (l > mid)
Mul(R[p], l, r, mid + 1, nr);
else
Mul(L[p], l, mid, nl, mid), Mul(R[p], mid + 1, r, mid + 1, nr);
push_up(p);
}
} T;
int n, m, l[N], r[N], id[N];
LL S[11][11], fac[11], Ans;
inline bool cmp(int A, int B) {
return l[A] < l[B];
}
int main() {
redn(n), redn(k);
m = (n << 1) + 1;
T.Bld(T.rt, 0, m);
forn(i, 1, n) redn(l[i]), redn(r[i]), id[i] = i;
sort(id + 1, id + n + 1, cmp);
trans[0] = 1;
T.Upd(T.rt, 0, m, 0);
forn(i, 1, n) {
forn(j, 0, k) wgt[j] = 0;
T.Qry(T.rt, 0, l[id[i]] - 1, 0, m);
trans[0] = wgt[0];
forn(j, 1, k) trans[j] = wgt[j] + wgt[j - 1], trans[j] %= Mod;
forn(j, 0, k) wgt[j] = 0;
T.Qry(T.rt, l[id[i]], r[id[i]], 0, m);
forn(j, 0, k) trans[j] = trans[j] + wgt[j], trans[j] %= Mod;
T.Upd(T.rt, 0, m, r[id[i]]);
T.Mul(T.rt, r[id[i]] + 1, m, 0, m);
forn(j, 0, k) wgt[j] = 0ll;
T.Qry(T.rt, 0, m, 0, m);
}
forn(i, 0, k) wgt[i] = 0;
T.Qry(T.rt, 0, m, 0, m);
S[0][0] = 1;
forn(i, 1, k) forn(j, 1, k) S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j] % Mod) % Mod;
fac[0] = 1ll;
forn(i, 1, k) fac[i] = 1ll * i * fac[i - 1] % Mod;
forn(i, 0, k) Ans += S[k][i] * fac[i] % Mod * wgt[i] % Mod, Ans %= Mod;
printf("%lld
", Ans);
return 0;
}