- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
سروش یک دفتر دارد که روی هر ورق آن یک عدد طبیعی با خودکار آبی نوشته است. سپس پیمان دفتر سروش را بر می‌دارد و روی هر ورق آن یک عددی دیگر با خودکار قرمز می‌نویسد که برابر با یکی از دو حالت زیر است:
- جمع عددهای ورق‌ها از اول دفتر تا همین صفحه (شامل همین صفحه)
- جمع عددهای ورق‌ها از آخر دفتر تا همین صفحه (شامل همین صفحه)
سپس کیوان تمام ورق‌ها را از دفتر جدا می‌کند و ترتیب آن‌ها را خراب می‌کند. حال رضا برای خوشحالی سروش تصمیم می‌گیرد با توجه به عددهایی که روی برگه‌ها نوشته شده، برگه‌ها را به ترتیب اولیه قرار دهد. اما محمد به رضا می‌گوید این کار با بیش از یک روش انجام می‌گیرد. رضا از علی می‌پرسد به چند شکل ممکن می‌توان ورق‌ها را چید که عدد قرمز هر ورق، برابر با جمع عددهای آبی ورق‌ها از ابتدا تا این ورق یا از انتها تا این ورق باشد. به علی کمک کنید جواب رضا را بدهد. با توجه به اینکه این مقدار ممکن است خیلی زیاد باشد، باقی‌مانده‌ی آن در تقسیم بر $10^9 + 7$ را چاپ کنید.
ورودی
در خط اول ورودی یک عدد طبیعی آمده است که تعداد ورق‌های دفتر را نشان می‌دهد.
$$1 \leq n \leq 1000$$
در $n$ خط بعدی، در خط $i$ام، دو عدد طبیعی $b_i$ و $r_i$ آمده است که به ترتیب عدد آبی و عدد قرمز روی یکی از ورق‌ها را نشان می‌دهد.
$$1 \leq b_i \leq 10^6$$ $$1 \leq r_i \leq 10^9$$
تضمین می‌شود حداقل به یک روش می‌توان ورق‌ها را مرتب کرد طوری که شرط مسئله برقرار باشد.
خروجی
در تنها خط خروجی، باقی‌مانده‌ی تعداد حالت‌هایی که ممکن است ورق‌ها در ابتدا در دفتر قرار داشته باشند را در تقسیم بر $10^9 + 7$ چاپ کنید.
مثال‌ها
ورودی نمونه ۱
3
2 3
1 1
3 6
خروجی نمونه ۱
2
ورودی نمونه ۲
4
4 16
4 16
4 8
4 8
خروجی نمونه ۲
4
ورودی نمونه ۳
7
1 1
2 27
3 6
4 22
5 18
6 21
7 7
خروجی نمونه ۳
2
ارسال پاسخ برای این سؤال