Mike and Geometry Problem

3000ms

262144K

Description:

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 $\text{[math]}$ ). You are given two integers n and k and n closed intervals [l_i, r_i] on OX axis and you have to find:

$\text{[math]}$

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 (10⁹ + 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 l_i, r_i ( - 10⁹ ≤ l_i ≤ r_i ≤ 10⁹), describing i-th segment bounds.