Mike想为IMO做准备,但他不懂几何,所以他的老师给了他一个有趣的几何问题。我们将 f([l, r]) = r - l + 1 定义为段 [l, r] 中 l ≤ r 的整数点数(假设 $$f(\varnothing) = 0$$)。给定两个整数 n 和 k 以及 OX 轴上的 n 个闭区间 [li, ri],你必须找到:
$$\sum_{1 \leq i_1 < i_2 < \ldots < i_k \leq n} f([l_{i_1}, r_{i_1}] \cap [l_{i_2}, r_{i_2}] \cap \ldots \cap [l_{i_k}, r_{i_k}])$$
换句话说,您应该找到任意 k 个线段的交集中的整数点数之和。
由于答案可能非常大,因此输出它对 1000000007 (109 + 7) 取模。
迈克无法解决这个问题,所以他需要你的帮助。你会帮助他,不是吗?
输入
第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 200 000)——分别是路段数和路口组中的路段数。
接下来是 n 行,第 i 行包含两个整数 li, ri ( - 109 ≤ li ≤ ri ≤ 109),描述第 i 个段边界。
输出
打印一个整数——迈克问题的答案,在唯一的一行中对 1000000007 (109 + 7) 求模。
示例
输入 #1
3 2 1 2 1 3 2 3
输出 #1
5
输入 #2
3 3 1 3 1 3 1 3
输出 #2
3
输入 #3
3 1 1 2 2 3 3 4
输出 #3
6
注意
在第一个示例中:
$$f([1,2]\cap[1,3])=f([1,2])=2$$;
$$f([1,2]\cap[2,3])=f([2,2])=1$$;
$$f([1,3]\cap[2,3])=f([2,3])=2$$。
所以答案是 2 + 1 + 2 = 5。