Solution

先将所有线段按左端点排序。

定义 $f_{r, k}$ 为表示最右以 $r$ 结尾的线段集合的连通块的数量的 $k$ 次的和。假设各个方案的一次分别为 a, b, c…，则 $f_{r, k}$ 形如 $a^k + b^k + c^k...$。

我们插入一条线段 [l, r]。

当 $i < l$, 对于这些方案，插入的线段会使连通块数量加 1 ( 每种方案都 + 1，其它题解直接写 (x + 1) ^ k 让蒟蒻卡了好久没理解 )。

是这样的，我们即要把 $(a + 1)^k + (b + 1)^k + (c + 1)^k...$ 加到 $f_{r, k}$ 中，二项式定理展开即为

$\binom{k}{0}(1 + 1 + 1 ...) + \binom{k}{1}(a + b + c ...) + ... + \binom{k}{k}(a ^ k + b ^ k + c ^ k ...)$

明显对于以同一个组合数为系数的形如 $a^j + b^j + c^j...$, 我们之前就用 $f_{i, j}$ 记录好了，所以我们可以 $O(k^2)$ 转移出 $f_{r, k}$, 但由于有多个 $i$， 可以用线段树求和。

当 $l < i < r$, 和新线段相交，直接加到 $f_{r, k}$。

当 $i > r$, 由于按左端点排了序，新线段一定被包含，选不选不影响连通块数目，直接把这些 $f_i$ 乘以 $2$， 也是用线段树实现。

#include <bits/stdc++.h>
#define mod 1000000007
using ll = long long;
using namespace std;
const int N = 1e5 + 10;
int n, k;
ll C[15][15];
struct node {
    int l, r;
    bool operator < (const node & b) const {
        return l < b.l;
    }
} a[N];
struct P {
    vector<ll> p;
    P () {p.resize(11);}
    P operator + (const P & b) const {
        P x;
        for(int i = 0; i <= k; ++i) x.p[i] = (p[i] + b.p[i]) % mod;
        return x;
    }
    P operator * (const ll & b) const {
        P x;
        for(int i = 0; i <= k; ++i) x.p[i] = (p[i] * b) % mod;
        return x;
    }
} ;
struct Segment {
    P d[N << 3];
    ll tag[N << 3];
    Segment () {for(int i = 0; i < (N << 2); ++i) tag[i] = 1;}
    void pushdown(int&p) {
        if(tag[p] == 1) return ;
        tag[p << 1] = tag[p << 1] * tag[p] % mod;
        tag[p << 1 | 1] = tag[p << 1 | 1] * tag[p] % mod;
        d[p << 1] = d[p << 1] * tag[p];
        d[p << 1 | 1] = d[p << 1 | 1] * tag[p];
        tag[p] = 1;
    }
    void merge(int p) {
        d[p] = d[p << 1] + d[p << 1 | 1];
    }
    void mul(int&l, int&r, int s, int t, int p) {
        if(l <= s && t <= r) {
            tag[p] = tag[p] * 2 % mod;
            d[p] = d[p] * 2;
            return ;
        }
        pushdown(p);
        int mid = (s + t) >> 1;
        if(l <= mid) mul(l, r, s, mid, p << 1);
        if(r > mid) mul(l, r, mid + 1, t, p << 1 | 1);
        merge(p);
    }
    void update(int&g, int s, int t, int p, P&x) {
        if(s == t) {
            d[p] = x;
            return ;
        }
        pushdown(p);
        int mid = (s + t) >> 1;
        if(g <= mid) update(g, s, mid, p << 1, x);
        else update(g, mid + 1, t, p << 1 | 1, x);
        merge(p);
    }
    P query(int l, int r, int s, int t, int p) {
        if(l <= s && t <= r) {
            return d[p];
        }
        pushdown(p);
        P ret;
        int mid = (s + t) >> 1;
        if(l <= mid) ret = ret + query(l, r, s, mid, p << 1);
        if(r > mid) ret = ret + query(l, r, mid + 1, t, p << 1 | 1);
        return ret;
    }
} tree;
void init() {
    C[0][0] = 1;
    for(int i = 1; i <= 10; ++i) {
        C[i][0] = 1;
        for(int j = 1; j <= i; ++j) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
}
void solve() {
    init();
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) cin >> a[i].l >> a[i].r;
    sort(a + 1, a + n + 1);
    int R = 2 * n;
    for(int i = 1; i <= n; ++i) {
        int l = a[i].l, r = a[i].r;
        tree.mul(r, R, 1, R, 1); //给后面都乘以2
        P ret = tree.query(l, r, 1, R, 1), tmp = tree.query(1, l, 1, R, 1);
        for(int j = 0; j <= k; ++j) {
            ret.p[j] = (ret.p[j] + 1) % mod; //只选择新线段
            for(int c = 0; c <= j; ++c) {
                ret.p[j] = (ret.p[j] + C[j][c] * tmp.p[c] % mod) % mod;
            }
        }
        tree.update(r, 1, R, 1, ret);
    }
    ll ans = 0;
    for(int i = 1; i <= R; ++i) {
        ans = (ans + tree.query(i, i, 1, R, 1).p[k]) % mod;
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}