//File Name: cf689E.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年07月11日 星期一 18时44分40秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <queue>

#define LL long long

using namespace std;

const int MAXN =  + ;

const int MAXN2 =  + ;

const int MOD = (int)1e9 + ;

const int INF = 0x3f3f3f3f;

struct Line{

    int l,r;

    bool operator<(const Line &a)const{

        if(a.r == r) return a.l < l;

        return a.r < r;

    }

}line[MAXN];

int g[MAXN2],s[MAXN2];

LL jie[MAXN2];

void init(){

    jie[] = ;

    for(int i=;i<MAXN2;i++)

        jie[i] = jie[i-] * i % MOD;

    memset(g,,sizeof g);

    memset(s,,sizeof s);

}

LL qp(LL x,LL y){

    LL res = ;

    while(y){

        if(y & ) res = res * x % MOD;

        x = x * x % MOD;

        y >>= ;

    }

    return res;

}

LL get_C(int x,int y){

    if(x <  || x < y) return ;

    if(y ==  || y == x) return ;

    return jie[x] * qp(jie[y] * jie[x - y] % MOD,MOD - ) % MOD;

}

bool cmp(Line x,Line y){

    if(x.l == y.l)

        return x.r < y.r;

    return x.l < y.l;

}

LL solve(int N,int K){

    sort(line,line+N,cmp);

    line[N].l = INF;

    int tot = ,sum = ,now = line[].l;

    int iter = ;

    priority_queue<Line> que;

    while(!que.empty()) que.pop();

    while(!(iter == N && que.empty())){

        while(iter < N && line[iter].l <= now){

            que.push(line[iter]);

            sum++;

            iter++;

        }

        int now_r = que.top().r;

        //printf("now_r = %d sum = %d iter = %d\n",now_r,sum,iter);

        if(now_r < line[iter].l){

            g[++tot] = now_r - now + ;

            s[tot] = sum;

            now = now_r + ;

            //puts("1111111");

        }

        else{

            g[++tot] = line[iter].l - now;

            s[tot] = sum;

            now = line[iter].l;

            //puts("222222222222");

        }

        while(sum && que.top().r < now){

            que.pop();

            sum--;

        }

        if(que.empty())

            now = line[iter].l;

    }

    LL ans = ;

    for(int i=;i<=tot;i++){

        ans = (ans + get_C(s[i],K) * g[i] % MOD) % MOD;

    }

    return ans;

}

int main(){

    init();

    int n,k;

    while(~scanf("%d %d",&n,&k)){

        for(int i=;i<n;i++){

            scanf("%d %d",&line[i].l,&line[i].r);

        }

        printf("%d\n",(int)solve(n,k));

    }

    return ;

}