Mike wants to prepare for IMO but he doesn't know geometry, so his teacher gave him an interesting geometry problem. Let's define f([l, r]) = r - l + 1 to be the number of integer points in the segment [l, r] with l ≤ r (say that <image>). You are given two integers n and k and n closed intervals [li, ri] on OX axis and you have to find:

<image>

In other words, you should find the sum of the number of integer points in the intersection of any k of the segments. 

As the answer may be very large, output it modulo 1000000007 (109 + 7).

Mike can't solve this problem so he needs your help. You will help him, won't you? 

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 200 000) — the number of segments and the number of segments in intersection groups respectively.

Then n lines follow, the i-th line contains two integers li, ri ( - 109 ≤ li ≤ ri ≤ 109), describing i-th segment bounds.

Output

Print one integer number — the answer to Mike's problem modulo 1000000007 (109 + 7) in the only line.

Examples

Input

3 2
1 2
1 3
2 3


Output

5


Input

3 3
1 3
1 3
1 3


Output

3


Input

3 1
1 2
2 3
3 4


Output

6

Note

In the first example: 

<image>;

<image>;

<image>.

So the answer is 2 + 1 + 2 = 5.
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const double pi = acos(-1.0), eps = 1e-6;
void File() {
  freopen("D:\\in.txt", "r", stdin);
  freopen("D:\\out.txt", "w", stdout);
}
template <class T>
inline void read(T &x) {
  char c = getchar();
  x = 0;
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
}
long long mod = 1e9 + 7;
const int maxn = 2000010;
int n, k;
long long f[maxn], a[maxn];
struct X {
  int L, R;
} s[maxn];
int c[maxn], b[maxn], sz;
long long ans[maxn];
int lowbit(int x) { return x & (-x); }
int sum(int x) {
  int res = 0;
  while (x > 0) res = res + c[x], x = x - lowbit(x);
  return res;
}
void update(int x, int v) {
  while (x <= 1500000) c[x] = c[x] + v, x = x + lowbit(x);
}
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0 && b == 0) return -1;
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extend_gcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
long long mod_reverse(long long a, long long n) {
  long long x, y;
  long long d = extend_gcd(a, n, x, y);
  if (d == 1)
    return (x % n + n) % n;
  else
    return -1;
}
int get(int x) {
  int L = 0, R = sz - 1, pos = 0;
  while (L <= R) {
    int mid = (L + R) / 2;
    if (b[mid] < x)
      L = mid + 1;
    else if (b[mid] == x)
      pos = mid, R = mid - 1;
    else
      R = mid - 1;
  }
  return pos + 1;
}
bool cmp(X a, X b) { return a.L < b.L; }
int main() {
  scanf("%d%d", &n, &k);
  f[0] = 1;
  for (int i = 1; i <= 1500000; i++) f[i] = i * f[i - 1] % mod;
  for (int i = k; i <= 1500000; i++) {
    long long fz = f[i] % mod, fm = f[k] * f[i - k] % mod;
    long long ni = mod_reverse(fm, mod);
    a[i] = fz * ni % mod;
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &s[i].L, &s[i].R);
    b[sz++] = s[i].L, b[sz++] = s[i].R;
    b[sz++] = s[i].L - 1;
    b[sz++] = s[i].L + 1;
    b[sz++] = s[i].R - 1;
    b[sz++] = s[i].R + 1;
  }
  sort(b, b + sz);
  sort(s + 1, s + 1 + n, cmp);
  int h = 1;
  for (int i = 1; i <= sz; i++) {
    while (h <= n && get(s[h].L) == i) {
      update(get(s[h].R), 1);
      h++;
    }
    ans[i] = a[sum(1500000) - sum(i - 1)];
  }
  long long Ans = 0;
  for (int i = 0; i < sz;) {
    int pos = -1;
    for (int j = i; j < sz; j++) {
      if (b[j] > b[i]) {
        pos = j;
        break;
      }
    }
    if (pos == -1) {
      Ans = (Ans + ans[i + 1]) % mod;
      break;
    }
    Ans = (Ans + (b[pos] - b[i]) * ans[i + 1] % mod) % mod;
    i = pos;
  }
  printf("%lld\n", Ans);
  return 0;
}
