Допоможи собі сам#10124

Допоможи собі сам

1 секунда

128 мегабайтів

Дуже легка

Бессі має $n$ відрізків на одновимірній числовій прямій. $i$ -ий відрізок включає всі дійсні числа $x$ , для яких виконується нерівність $l_{i} \leq x \leq r_{i}$ l_i \le x \le r_i. Об'єднання відрізків визначається як набір всіх $x$ , що належать хоча б одному з цих відрізків. Складність набору відрізків визначається як кількість зв'язаних областей, що утворюються в результаті їх об'єднання.

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

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

Вхідні дані

Перша стрічка містить число $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5). Кожна з наступних $n$ стрічок містить два цілі числа $l_{i}$ l_i і $r_{i}$ r_i. Гарантовано, що $l_{i} < r_{i}$ l_i < r_i і всі $l_{i}, r_{i}$ l_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]} ⟹ 2
{[1, 6], [2, 3], [4, 5]} ⟹ 1

Відповідь дорівнює $1 + 1 + 1 + 1 + 1 + 2 + 1 = 8$ 1 + 1 + 1 + 1 + 1 + 2 + 1 = 8.

Приклад 1