+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- شنل‌قرمزی یک گراف‌کار قوی است. او $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 ```