先将所有线段按右端点排序。考虑 DP，设 f_i 为最后选了线段 i 的答案。假设现在正在转移第 i 条线段，枚举上一条被选的线段 j ，那么 j 与 i 的关系有三种：

• j 被 i 包含（l_j>l_i）。此时选不选 j 都是等效的，但不能直接从 j 转移（因为连通块数不确定）。可以记下这种情况的贡献，在后面转移时统计。设 g_k=\sum_{j>k}[l_j>l_i]，那么转移 k 时乘上 2^{g_k} 即可。

• j 与 i 相交但不被包含（l_j<l_i,r_j>r_i）。此时加上线段 i 后的连通块个数与 f_j 相比既不会增加也不会减少，所以直接将 f_j 乘上第一种情况的贡献加到 f_i 上即可，即f_i\leftarrow f_j\cdot 2^{g_j}。

• j 与 i 不相交（r_j<l_i）。此时连通块个数会 +1，然而我们不是很好求转移后的 K 次方和。所以我们可以将 f_i 扩展一维变成 f_i(k) 表示连通块数的 k 次方和，再用二项式定理转移。具体地，设 adv(St) 表示状态 St 连通块数 +1 后转移到的状态，则 adv(St)(k)=\sum_{p}(c_p+1)^k=\sum_{t=0}^{k}\binom{k}{t}\sum_p{c_p^t}=\sum_{t=0}^{k}\binom{k}{t}St(t)

  然后还要乘上第一种情况的贡献再加到 f_i 上，即 f_i\leftarrow adv(f_j)\cdot 2^{g_j}。

从大到小枚举 j ，我们就有了一个 O(n(n+k^2)) 的暴力。但我们还可以继续优化。

第二种情况需要在线段树上维护满足条件的 f_j 的和以及 g_j 对它的贡献的乘积。考虑加入线段 k 时，将 [1,l_k-1] 乘上 2，将 [l_k,r_k] 加上 f_k，转移时单点查 l_i 的值即可。

第三种情况，由于 r_j<l_i ，比较容易看出这种情况的 g_j 都是相等的。用树状数组维护以下 f_j(r_j\leq l_i) 的前缀和以及满足 l_k>l_i 的 k 的个数就可以直接算了。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=110000;
const int MAXK=11;
const int P=1E9+7;
struct Segment
{
    int l, r;
    Segment(int x=0): r(x) {}
    bool operator < (const Segment& rhs) const
    {
        return r<rhs.r;
    }
} a[MAXN];
int n, k;
int c[MAXK][MAXK];
int pow2[MAXN];
struct Status
{
    int v[MAXK];
    Status() { clear(); }
    void clear() { memset(v, 0, sizeof v); }
    Status operator + (const Status& rhs) const
    {
        Status ret;
        for (int i=0; i<=k; i++)
            ret.v[i]=(v[i]+rhs.v[i])%P;
        return ret;
    }
    Status operator * (int x) const
    {
        Status ret;
        for (int i=0; i<=k; i++)
            ret.v[i]=1ll*v[i]*x%P;
        return ret;
    }
    Status trans() const
    {
        Status ret;
        for (int i=0; i<=k; i++)
            for (int j=0; j<=i; j++)
                ret.v[i]=(ret.v[i]+1ll*c[i][j]*v[j])%P;
        return ret;
    }
} f[MAXN];
inline int lb(int x) { return x&-x; }
template<typename T>
struct BIT
{
    T s[2*MAXN];
    void add(int x, const T& k)
    {
        while (x<=2*n) s[x]=s[x]+k, x+=lb(x);
    }
    T sum(int x)
    {
        T r=T();
        while (x>0) r=r+s[x], x-=lb(x);
        return r; 
    }
};
BIT<Status> bit1;
BIT<int> bit2;
struct SegmentTree
{
    struct Node
    {
        int l, r;
        int mul; Status add;
    } tr[8*MAXN];
    #define lc (o<<1)
    #define rc (o<<1|1)
    void update(int o, int a, const Status& b)
    {
        tr[o].mul=1ll*tr[o].mul*a%P;
        tr[o].add=tr[o].add*a+b;
    }
    void pushdown(int o)
    {
        update(lc, tr[o].mul, tr[o].add);
        update(rc, tr[o].mul, tr[o].add);
        tr[o].mul=1, tr[o].add.clear();
    }
    void build(int o, int l, int r)
    {
        tr[o].l=l, tr[o].r=r;
        tr[o].mul=1, tr[o].add.clear();
        if (l==r) return;
        int mid=l+r>>1;
        build(lc, l, mid);
        build(rc, mid+1, r);
    }
    void modify(int o, int l, int r, int a, const Status& b)
    {
        if (tr[o].l>r||tr[o].r<l) return;
        if (l<=tr[o].l&&tr[o].r<=r) { update(o, a, b); return; }
        modify(lc, l, r, a, b);
        modify(rc, l, r, a, b);
    }
    Status query(int o, int p)
    {
        if (tr[o].l==tr[o].r) return tr[o].add;
        pushdown(o);
        int mid=tr[o].l+tr[o].r>>1;
        if (p<=mid) return query(lc, p);
        else return query(rc, p);
    }
    #undef lc
    #undef rc
} sgt;
int main()
{
    freopen("help.in", "r", stdin);
    freopen("help.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for (int i=0; i<=k; i++)
    {
        c[i][0]=1;
        for (int j=1; j<=i; j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    pow2[0]=1;
    for (int i=1; i<=n; i++) pow2[i]=2*pow2[i-1]%P;
    for (int i=1; i<=n; i++)
        scanf("%d%d", &a[i].l, &a[i].r);
    sort(a+1, a+n+1);
    f[0].v[0]=1; bit1.add(1, f[0]);
    sgt.build(1, 1, 2*n);
    for (int i=1; i<=n; i++)
    {
        f[i]=bit1.sum(a[i].l).trans()*pow2[bit2.sum(2*n-a[i].l)]+sgt.query(1, a[i].l);
        bit1.add(a[i].r+1, f[i]);
        bit2.add(2*n-a[i].l, 1);
        sgt.modify(1, 1, a[i].l-1, 2, Status());
        sgt.modify(1, a[i].l, a[i].r, 1, f[i]);
    }
    int ans=0;
    for (int i=0; i<=n; i++) ans=(ans+f[i].v[k])%P;
    printf("%d\n", ans);
    return 0;
}