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