کار ساخت آزادراه به پایان رسیده و برای ایجاد روشنایی راه، چراغهایی در طول مسیر گذاشته شده است. آقای مهندس که در مناقصهی این پروژه شکست خورده بود، اکنون که پروژه به پایان رسیده به دنبال نقصهای آن است. او اعتقاد دارد چراغهایی که برای آزادراه به کار رفتهاند بیش از حد نیاز هستند و برای همین تعداد زیرمجموعههایی از چراغها که باعث روشنایی کل مسیر میشوند را میخواهد.
آزادراه را میتوان به صورت بازهی در نظر گرفت که هر کدام از چراغها یک بازهی از آن را روشن میکنند. برنامهای بنویسید که با گرفتن اطلاعات مریوط به آزادراه، تعداد زیرمجموعههایی از چراغها که کل آزادراه را روشن میکنند، محاسبه کند. با توجه به اینکه این مقدار ممکن است خیلی بزرگ باشد، باقیماندهی آن را بر محاسبه کنید.
در سطر اول ورودی به ترتیب دو عدد طبیعی ، تعداد چراغهای آزادراه و ، طول خیابان، آمده است.
در هریک از سطر بعدی به ترتیب دو عدد طبیعی و آمده است که محدودهی روشنایی یک چراغ را مشخص میکنند.
در تنها سطر خروجی باقیماندهی تعداد زیرمجموعههایی که باعث روشنایی کل آزادراه میشوند را بر چاپ کنید.
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۱۰ | |
۲ | ۱۵ | |
۳ | ۱۵ | |
۴ | ۶۰ | بدون محدودیت اضافی |
۲۴امین دوره المپیاد کامپیوتر - آزمون ششم - ۱۳۹۳/۰۶/۱۷