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

Бессі отримала 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] різні та знаходяться в діапазоні від 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.

Приклади