← 返回题目列表

Codeforces · 689/E

E. 迈克和几何问题

中文机器翻译题面 查看原题

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。