Özünə kömək et#10124

Özünə kömək et

1 saniyə

128 meqabayt

Çox asan

Bessi $n$ ədəd 1D seqmenti düz xətt üzərində yerləşdirib. $i$ -ci seqment $l_{i} \leq x \leq r_{i}$ l_i \le x \le r_i olan bütün həqiqi ədədləri əhatə edir. Seqmentlərin birləşməsini, ən azı bir seqmentdə olan bütün $x$ ədədlərinin dəsti kimi müəyyən edək. Seqmentlər dəstinin mürəkkəbliyi, onun birləşməsində təmsil olunan əlaqəli sahələrin sayı kimi müəyyən edilir.

Bessi, verilmiş $n$ seqmentdən ibarət dəstin bütün $2^{n}$ 2^n alt dəstələri üzrə mürəkkəbliklərin cəmini $1 0^{9} + 7$ 10^9 + 7 modulu ilə hesablamaq istəyir.

Adətən sənin işin Bessiyə kömək etməkdir. Amma bu dəfə sən Bessisən və sənə kömək edən yoxdur. Özünə kömək et!

Giriş

Birinci sətir $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) ədədini ehtiva edir. Sonrakı $n$ sətirin hər biri iki tam ədəd $l_{i}$ l_i və $r_{i}$ r_i ehtiva edir. $l_{i} < r_{i}$ l_i < r_i və bütün $l_{i}, r_{i}$ l_i, r_i ədədlərinin $1...2 n$ aralığında fərqli tam ədədlər olduğu təmin edilir.

Çıxış

Cavabı $1 0^{9} + 7$ 10^9 + 7 modulu ilə çıxarın.

Nümunələr

Hər bir boş olmayan alt dəstənin mürəkkəbliyi aşağıda verilmişdir.

{[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

Cavab $1 + 1 + 1 + 1 + 1 + 2 + 1 = 8$ 1 + 1 + 1 + 1 + 1 + 2 + 1 = 8 bərabərdir.

Nümunə 1