Помоги себе (Платина)

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

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

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

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

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

Первая строка содержит n (1 ≤ n ≤ 10^5) и k (2 ≤ k ≤ 10). Каждая из следующих n строк содержит два целых числа l[i] и r[i]. Гарантируется, что l[i] < r[i] и все значения l[i], r[i] различны и находятся в промежутке 1..2n.

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

Выведите ответ по модулю 10^9 + 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.

Примеры