CF689E.Mike and Geometry Problem

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 ). You are given two integers n and k and n closed intervals [l__i, r__i] on OX axis and you have to find:

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?

Mike 想为国际数学奥林匹克竞赛（IMO）做准备，但他不会几何，因此他的老师给了他一道有趣的几何题。我们定义函数 $f([l,\,r]) = r - l + 1$ 表示闭区间 $[l,\,r]$（其中 $l \le r$）中所含整数点的个数（即 ）。现给定两个整数 $n$ 和 $k$，以及 $n$ 个位于 $OX$ 轴上的闭区间 $[l_i,\,r_i]$，你需要计算：

换言之，你需要求出：在所有 $\binom{n}{k}$ 种选取 $k$ 个区间的方案中，每种方案所选 $k$ 个区间交集内的整数点个数之和。

由于答案可能非常大，请将结果对 $1000000007$（即 $10^9 + 7$）取模后输出。

Mike 解不出这道题，所以他需要你的帮助。你愿意帮他吗？

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 l__i, r__i ( - 109 ≤ l__i ≤ r__i ≤ 109), describing i-th segment bounds.

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 200\,000$），分别表示线段的总数以及交集组中所含线段的数量。

接下来有 $n$ 行，其中第 $i$ 行包含两个整数 $l_i$、$r_i$（$-10^9 \le l_i \le r_i \le 10^9$），描述第 $i$ 条线段的左右端点。

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

在单独的一行中输出一个整数——Mike 问题的答案对 1000000007（$10^9 + 7$）取模的结果。

In the first example:

;

;

.

So the answer is 2 + 1 + 2 = 5.

在第一个例子中：

;

;

。

因此答案为 $2 + 1 + 2 = 5$。