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

---

شنل‌قرمزی یک گراف‌کار قوی است. او $n$ بازه به شکل $[ l_i, r_i ]$ دارد. حال او گرافی $n$ راسی ساخته‌است که راس $i$ اُم متناظر با بازه‌ی $i$ اُم است. او بین دو راس $u$ و $v$ یال می‌گذارد، اگر و فقط اگر بازه‌ی $u$ و $v$ اشتراک داشته باشند (یعنی $max( l_u , l_v ) \le min( r_u , r_v )$ ). حال او از شما می‌خواهد تا تعداد مجموعه‌های غالب Dominating Set این گراف را بیابید.

مجموعه‌ی $S$ متشکل از تعدادی از رئوس گراف، مجموعه‌ی غالب است اگر و تنها اگر هر راس $v$ در $G$ یا عضو $S$ باشد یا یکی از همسایه‌هایش عضو $S$ باشد.

ورودی

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

در $n$ خط بعدی $l_i$ و $r_i$، شروع و پایان بازه‌ی $i$ ام آمده‌است. $$1 \le n \le 5\ 000$$ $$0 \le l_i \le r_i \le 10\ 000$$

خروجی

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

زیرمسئله‌ها

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

مثال

ورودی نمونه ۱

2
1 5
3 3

خروجی نمونه ۱

3

ورودی نمونه ۲

3
1 3 
2 5
4 6

خروجی نمونه ۲

5