+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ----- کار ساخت آزاد‌راه به پایان رسیده و برای ایجاد روشنایی راه، چراغ‌هایی در طول مسیر گذاشته شده است. آقای مهندس که در مناقصه‌ی این پروژه شکست خورده بود، اکنون که پروژه به پایان رسیده به دنبال نقص‌های آن است. او اعتقاد دارد چراغ‌هایی که برای آزادراه به کار‌ رفته‌اند بیش از حد نیاز هستند و برای همین تعداد زیر‌مجموعه‌هایی از چراغ‌ها که باعث روشنایی کل مسیر می‌شوند را می‌خواهد. آزاد‌راه را می‌توان به صورت بازه‌ی $[0,l]$ در نظر گرفت که هر کدام از چراغ‌ها یک بازه‌ی $[s,e]$ از آن‌ را روشن می‌کنند. برنامه‌ای بنویسید که با گرفتن اطلاعات مریوط به آزاد‌راه، تعداد زیر‌مجموعه‌هایی از چراغ‌ها که کل آزاد‌راه را روشن می‌کنند، محاسبه کند. با توجه به این‌که این مقدار ممکن است خیلی بزرگ باشد، باقی‌مانده‌ی آن را بر $10^9 + 7$ محاسبه کنید. # ورودی در سطر اول ورودی به ترتیب دو عدد طبیعی $n$، تعداد چراغ‌های آزاد‌راه و $l$، طول خیابان، آمده است. در هریک از $n$ سطر بعدی به ترتیب دو عدد طبیعی $s$ و $e$ آمده است که محدوده‌ی روشنایی‌ یک چراغ را مشخص می‌کنند. $$1\le n, l\le 200\ 000$$ $$0 \le s < e \leq l$$ # خروجی در تنها سطر خروجی باقی‌مانده‌ی تعداد زیر‌مجموعه‌هایی که باعث روشنایی کل آزادراه می‌شوند را بر $10^9 + 7$ چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۱۰ | $ l \le 500, n \le 15$ | | ۲ | ۱۵ | $ l \le 500, n \le 500$ | | ۳ | ۱۵ | $ l \le 5\ 000, n \le 5\ 000$ | | ۴ | ۶۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 3 10 0 6 4 10 0 10 ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 5 5 0 5 0 5 0 5 0 5 0 5 ``` ## خروجی نمونه ۲ ``` 31 ``` ۲۴امین دوره‌ المپیاد کامپیوتر - آزمون ششم - ۱۳۹۳/۰۶/۱۷