سوال ۲

کار ساخت آزاد‌راه به پایان رسیده و برای ایجاد روشنایی راه، چراغ‌هایی در طول مسیر گذاشته شده است. آقای مهندس که در مناقصه‌ی این پروژه شکست خورده بود، اکنون که پروژه به پایان رسیده به دنبال نقص‌های آن است. او اعتقاد دارد چراغ‌هایی که برای آزادراه به کار‌ رفته‌اند بیش از حد نیاز هستند و برای همین تعداد زیر‌مجموعه‌هایی از چراغ‌ها که باعث روشنایی کل مسیر می‌شوند را می‌خواهد.

آزاد‌راه را می‌توان به صورت بازه‌ی $[0, l]$ در نظر گرفت که هر کدام از چراغ‌ها یک بازه‌ی $[s, e]$ از آن‌ را روشن می‌کنند. برنامه‌ای بنویسید که با گرفتن اطلاعات مریوط به آزاد‌راه، تعداد زیر‌مجموعه‌هایی از چراغ‌ها که کل آزاد‌راه را روشن می‌کنند، محاسبه کند. با توجه به این‌که این مقدار ممکن است خیلی بزرگ باشد، باقی‌مانده‌ی آن را بر $10^9 + 7$ محاسبه کنید.

• در سطر اول ورودی به ترتیب دو عدد طبیعی $n$، تعداد چراغ‌های آزاد‌راه و $l$، طول خیابان، آمده است.
• در هریک از $n$ سطر بعدی به ترتیب دو عدد طبیعی $s$ و $e$ آمده است که محدوده‌ی روشنایی‌ یک چراغ را مشخص می‌کنند.
• $1 \leq n, l \leq 2 * 10^5$
• $0 \leq s < e \leq l$

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

• زیرمسئله اول (۱۰ نمره): $n \leq 15$ و $l \leq 500$
• زیرمسئله دوم (۱۵ نمره): $n \leq 500$ و $l \leq 500$
• زیرمسئله سوم (۱۵ نمره): $n \leq 5000$ و $l \leq 5000$
• زیرمسئله چهارم (۶۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل