+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- در بندر یک ساحل، $n$ مدرسه وجود دارد. همه قایق های یک مدرسه یکسان و غیرقابل تشخیص‌اند اما قایق های مدرسه های مختلف رنگ های مختلفی دارند و از یکدیگر قابل تشخیص‌اند. در فستیوال تابستانی، هر مدرسه مانند مدرسه $i$ام تصمیم میگیرد یا قایقی نفرستد، یا هر تعداد قایق بین $a_i$ و $b_i$ بفرستد. ($a_i \leq b_i$) همچنین اگر مدرسه $i$ام تصمیم بگیرد قایق بفرستد، تعداد قایق های فرستاده شده توسط مدرسه $i$ باید از تعداد قایق های فرستاده شده توسط مدارس با شماره های کمتر از $i$، اکیدا بزرگتر باشد. تعداد حالت‌های فرستادن قایق توسط این $n$ مدرسه را بدست آورید در صورتی که حداقل یک مدرسه قایق بفرستد. # ورودی در خط اول $n$‌، تعداد مدرسه ها، به شما داده میشود. در $i$امین خط بعدی از $n$ خط، $a_i$ و $b_i$ داده میشود. $$1\leq n \leq 500$$ $$1\leq a_i \leq b_i \leq 10^9$$ # خروجی در تنها خط خروجی تعداد حالت های فرستادن قایق را چاپ کنید. چون این عدد ممکن است بزرگ باشد کافی است باقی مانده تقسیم آن بر $10^9+7$ را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۹ | $$a_i=b_i$$| | ۲ | ۲۲ | $$\sum b_i-a_i \leq 10^6$$| | ۳ | ۲۷ | $$n\leq100$$ | | ۴ | ۴۲ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 2 1 2 2 3 ``` ## خروجی نمونه ۱ ``` 7 ``` ۴ راه وجود دارد که تنها یک مدرسه قایق بفرستد. ۳ راه هم وجود دارد که هر دو مدرسه قایق بفرستند.