(Analysis by Benjamin Qi)

Sort the segments by left coordinate, and try placing the segments into a subset in this order. The only information we need to store about the collection of segments that are members of the subset is the rightmost coordinate in this collection.

For each $0\le i\le 2N$, $dp[i]$ will store information about collections with rightmost coordinate $i$. Suppose that collection $c$ contains exactly $a_c$ segments in this union. Then for each $0\le j\le K$ we'll store

So $dp[i][0]$ stores the number of collections with rightmost coordinate $i$, $dp[i][1]$ stores the sum of the number of segments in the union of each collection with rightmost coordinate $i$, and so on.

If we add a segment $[l,r]$ to a collection $c$ with rightmost coordinate $i$,

  1. If $i<l$ then $a_c$ increases by one and the rightmost coordinate becomes $r$.
  2. Otherwise if $i<r$ then $a_c$ remains unchanged and the rightmost coordinate becomes $r$.
  3. Otherwise $a_c$ and the rightmost coordinate remain unchanged.

To account for case 1, we need to find the updated value of $dp[i]$ after adding one to each $a_c$. Call the result $adv(dp[i]).$ By the binomial theorem,

This update can be performed in $O(K^2)$ time, giving a DP solution that runs in $O(N^2K^2)$ or $O(N^2+NK^2)$ time.

To receive full credit, use a lazy segment tree that supports point updates, range sum queries, and range multiplication updates.

  1. For case 1, add $adv\left(\sum_{i=0}^{l-1}dp[i]\right)$ to $dp[r]$.
  2. For case 2, add $\sum_{i=l}^{r-1}dp[i]$ to $dp[r]$.
  3. For case 3, multiply $dp[i]$ by two for each $i>r$.

After the above operations are performed for each segment, the final answer will be $\sum_{i=0}^{2N}dp[i][K]$. This can be done in $O(NK^2+NK\log N)$ time; the first term is for calculating $adv()$ and the second is for the range updates and queries. (In fact, it's possible to remove the $NK^2$ term, but I won't describe the method here.)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define f first
#define s second

const int MOD = 1e9+7; 

void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
struct mi {
  int v; explicit operator int() const { return v; }
  mi(ll _v) : v(_v%MOD) { v += (v<0)*MOD; }
  mi() : mi(0) {}
mi operator+(mi a, mi b) { return mi(a.v+b.v); }
mi operator-(mi a, mi b) { return mi(a.v-b.v); }
mi operator*(mi a, mi b) { return mi((ll)a.v*b.v); }
vector<pair<int,int>> v;
mi res;
int N,K;

typedef array<mi,11> T;
mi cum[11][11];
T adv(T p) {
  for (int i = K; i >= 0; --i) for (int j = i; j <= K; ++j)
    cum[i][j] = (i == j ? p[i] : cum[i][j-1]+cum[i+1][j]);
  T res; for (int i = 0; i <= K; ++i) res[i] = cum[0][i];
  return res;
T seg[1<<18];
mi lazy[1<<18];
vector<int> y = {0};
void push(int ind, int L, int R) {
  if (lazy[ind].v == 1) return;
  for (int i = 0; i <= K; ++i) seg[ind][i] = seg[ind][i]*lazy[ind];
  if (L != R) {
    lazy[2*ind] = lazy[2*ind]*lazy[ind];
    lazy[2*ind+1] = lazy[2*ind+1]*lazy[ind];
  lazy[ind] = 1;
void mul(int pos, int ind, int L, int R) {
  if (pos > R) return;
  if (pos <= L) {
    lazy[ind] = 2;
  int M = (L+R)/2;
  mul(pos,2*ind,L,M); mul(pos,2*ind+1,M+1,R);
  for (int i = 0; i <= K; ++i) seg[ind][i] = seg[2*ind][i]+seg[2*ind+1][i];
void upd(int pos, const T& val, int ind, int L, int R) {
  if (pos < L || pos > R) return;
  for (int i = 0; i <= K; ++i) seg[ind][i] = seg[ind][i]+val[i];
  if (L == R) return;
  int M = (L+R)/2;
  if (pos <= M) upd(pos,val,2*ind,L,M);
  else upd(pos,val,2*ind+1,M+1,R);
void query(int lo, int hi, T& t, int ind, int L, int R) {
  if (hi < L || lo > R) return;
  if (lo <= L && R <= hi) { 
    for (int i = 0; i <= K; ++i) t[i] = t[i]+seg[ind][i]; 
  int M = (L+R)/2;
  query(lo,hi,t,2*ind,L,M); query(lo,hi,t,2*ind+1,M+1,R);
void ad(int a, int b) {
  auto i1 = lower_bound(begin(y),end(y),a)-begin(y)-1;
  auto i2 = lower_bound(begin(y),end(y),b)-begin(y);
  T A = T(); query(0,i1,A,1,0,N); A = adv(A);
  T B = T(); query(i1+1,i2,B,1,0,N); 
  for (int i = 0; i <= K; ++i) A[i] = A[i]+B[i];
int main() {
  for (int i = 1; i < (1<<18); ++i) lazy[i] = 1;
  cin >> N >> K; v.resize(N); 
  for (auto& t: v) {
    cin >> t.f >> t.s;
  sort(begin(v),end(v)); sort(begin(y),end(y));
  T ori = T(); ori[0] = 1;
  for (auto t: v) ad(t.f,t.s);
  T res = T(); query(0,N,res,1,0,N);
  cout << res[K].v << "\n";