Майк готовится к IMO, но плохо знаком с геометрией, поэтому его учитель дал ему занимательную геометрическую задачу. Пусть f([l, r]) = r - l + 1 — число целых точек в отрезке [l, r] (l ≤ r) (считаем, что 
). Даны два числа n и k и n отрезков [li, ri] на оси Ox, и требуется посчитать
Другими словами, требуется посчитать сумму количеств целых точек в каждом из возможных пересечений любых k отрезков.
Так как искомое значение может быть очень большим, выведите его остаток от деления на 1000000007 (109 + 7).
Майк затрудняется решить эту задачу и нуждается в вашей помощи. Вы же не откажете ему в этом, не так ли?
В первой строке содержатся два целых числа n и k (1 ≤ k ≤ n ≤ 200 000) — количество отрезков и количество отрезков в рассматриваемых группах пересечений.
Затем следуют n строк, i-я из которых содержит два целых числа li, ri ( - 109 ≤ li ≤ ri ≤ 109), описывающих i-й отрезок.
В единственной строке выведите одно целое число — ответ на задачу Майка по модулю 1000000007 (109 + 7).
3 2
1 2
1 3
2 3
5
3 3
1 3
1 3
1 3
3
3 1
1 2
2 3
3 4
6
| Codeforces Round 361 (Div. 2) |
|---|
| Закончено |
