• محدودیت زمان: ۱.۵ ثانیه
  • محدودیت حافظه: ۵۱۲ مگابایت
  • منبع: آزمون نهایی سوم دوره ۲۷ المپیاد کامپیوتر

شنل‌قرمزی یک گراف‌کار قوی است. او nn بازه به شکل [li,ri][ l_i, r_i ] دارد. حال او گرافی nn راسی ساخته‌است که راس ii اُم متناظر با بازه‌ی ii اُم است. او بین دو راس uu و vv یال می‌گذارد، اگر و فقط اگر بازه‌ی uu و vv اشتراک داشته باشند (یعنی max(lu,lv)min(ru,rv)max( l_u , l_v ) \le min( r_u , r_v ) ). حال او از شما می‌خواهد تا تعداد مجموعه‌های غالب Dominating Set این گراف را بیابید.

مجموعه‌ی SS متشکل از تعدادی از رئوس گراف، مجموعه‌ی غالب است اگر و تنها اگر هر راس vv در GG یا عضو SS باشد یا یکی از همسایه‌هایش عضو SS باشد.

ورودی

در خط اول ورودی عدد nn، تعداد بازه‌ها آمده‌است.

در nn خط بعدی lil_i و rir_i، شروع و پایان بازه‌ی ii ام آمده‌است. 1n5 0001 \le n \le 5\ 000 0liri10 0000 \le l_i \le r_i \le 10\ 000

خروجی

در تنها سطر خروجی باقی‌مانده‌ی تعداد مجموعه‌های غالب بر 109+710^9+7 را چاپ کنید.

زیرمسئله‌ها

زیرمسئله نمره محدودیت
۱ ۱۲ n20n \le 20
۲ ۴۰ n100n \le 100
۳ ۴۸ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

2
1 5
3 3
Plain text

خروجی نمونه ۱

3
Plain text

ورودی نمونه ۲

3
1 3 
2 5
4 6
Plain text

خروجی نمونه ۲

5
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.