Mike and Geometry Problem

题意翻译

数轴上有 n 条线段，每条线段的端点为 $ l_i $ , $ r_i $。 众所周知，在 n 条线段中取 k 条线段有 $ n \choose k $ 即 $ C_n^k $ 种方案，现在每种方案的贡献为这 k 条线段交集包含的整点个数（即交集那条线段的长度 +1），求所有方案的贡献和mod 1e9+7。 感谢@nantf 提供的翻译

题目描述

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 $ ( $ 10^{9}+7 $ ). Mike can't solve this problem so he needs your help. You will help him, won't you?

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1<=k<=n<=200000 $ ) — 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^{9}<=l_{i}<=r_{i}<=10^{9}) $ , describing $ i $ -th segment bounds.

输出格式

Print one integer number — the answer to Mike's problem modulo $ 1000000007 $ ( $ 10^{9}+7 $ ) in the only line.

输入输出样例

输入样例 #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

说明

In the first example: ; ; . So the answer is $ 2+1+2=5 $ .