Бесси получила n отрезков на числовой прямой. i - ый отрезок содержит все вещественные числа x такие, что li ≤ x ≤ ri.

Определим объединение набора сегментов как набор всех x, содержащихся хотя бы в одном сегменте. Определим сложность набора отрезков как количество связанных регионов, представленных в их объединении, возведенное в степень k.

Бесси хочет вычислить сумму сложностей по всем 2n подмножествам данного набора n отрезков по модулю 109 + 7.

Обычно твоя работа - помогать Бесси. Но на этот раз ты Бесси, и помочь тебе некому. Помоги себе сам!

Входные данные

Первая строка содержит n (1 ≤ n ≤ 105) и k (2 ≤ k ≤ 10). Каждая из следующих n строк содержит два целых числа li и ri. Гарантируется, что li < ri и все значения li, ri различны и находятся в промежутке 1..2n.

Выходные данные

Выведите ответ по модулю 109 + 7.

Пример

Сложность каждого непустого подмножества приведена ниже.

{[1,6]} ⟹ 1, {[2,3]} ⟹ 1, {[4,5]} ⟹ 1

{[1,6],[2,3]} ⟹ 1, {[1,6],[4,5]} ⟹ 1, {[2,3],[4,5]} ⟹ 4

{[1,6],[2,3],[4,5]} ⟹ 1

Ответ равен 1 + 1 + 1 + 1 + 1 + 4 + 1 = 10.