eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

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

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

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

Первая строка содержит n (1n10^5) и k (2k10). Каждая из следующих 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.

Пример

Входные данные #1
3 2
1 6
2 3
4 5
Выходные данные #1
10
Источник 2020 USACO Февраль, Платина