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

---

در بندر یک ساحل، $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

۴ راه وجود دارد که تنها یک مدرسه قایق بفرستد. ۳ راه هم وجود دارد که هر دو مدرسه قایق بفرستند.