Допоможи собі (Платина)#10607

Допоможи собі (Платина)

1 секунда

128 мегабайтів

Дуже складна

Бессі отримала $n$ відрізків на числовій прямій. $i$ -ий відрізок містить усі дійсні числа $x$ , такі що $l_{i} \leq x \leq r_{i}$ l_i \leq x \leq r_i.

Об'єднанням набору відрізків називаємо множину всіх $x$ , що належать хоча б одному з відрізків. Складність набору відрізків визначається як кількість зв'язаних областей в їх об'єднанні, піднесена до степеня $k$ .

Бессі хоче обчислити суму складностей для всіх $2^{n}$ 2^n підмножин даного набору $n$ відрізків за модулем $1 0^{9} + 7$ 10^9 + 7.

Зазвичай ти допомагаєш Бессі, але цього разу ти сам є Бессі, і допомогти тобі нікому. Допоможи собі!

Вхідні дані

Перша строка містить $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) і $k$ ( $2 \leq k \leq 10$ 2 \leq k \leq 10). Кожен з наступних $n$ рядків містить два цілих числа $l_{i}$ l_i і $r_{i}$ r_i. Гарантується, що $l_{i} < r_{i}$ l_i < r_i, і всі значення $l_{i}$ l_i, $r_{i}$ r_i різні та знаходяться в діапазоні від $1$ до $2 n$ .

Вихідні дані

Виведіть відповідь за модулем $1 0^{9} + 7$ 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 + 1 + 1 + 1 + 1 + 4 + 1 = 10.

Приклад 1