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