Помоги себе (Платина)
Помоги себе (Платина)
Бесси получила 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.
3 2 1 6 2 3 4 5
10