آرایه گم‌شده


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

علی همیشه آرایه‌هایش را گم می‌کند. به همین منظور از روی آرایه‌ها برای خودش یک آرایه‌ی دیگر می‌سازد. به طور دقیق‌تر آرایه‌ای از اعداد صحیح مثل a1,a2,,ana_1, a_2, \dots, a_n\, را در نظر بگیرید. از روی آن آرایه‌ی b1,b2,,bnb_1, b_2, \dots, b_n\, را می‌سازد. به این صورت که برای هر ii از ۱ تا nn مقدار bib_i از رابطه‌ی زیر بدست می‌آید.

bi=max{a1,,ai}+min{a1,,ai}b_i = \max\{a_1, …, a_i\} + \min\{a_1, …, a_i\}

حال علی پیش از اینکه دنبال آرایه‌ی a1,a2,,ana_1, a_2, \dots, a_n\, بگردد، می‌خواهد از روی آرایه‌ی b1,b2,,bnb_1, b_2, \dots, b_n\, بررسی کند چند حالت برای آرایه‌ی اولیه وجود دارد.

به علی کمک کنید تا این تعداد را پیدا کند. چون ممکن است پاسخ مسئله خیلی بزرگ شود، باقی‌مانده این مقدار را به پیمانه‌ی 109+710^9 + 7 چاپ کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت nn داده می‌شود. 1n1000001 \leq n \leq 100 \, 000

در سطر دوم ورودی، nn عدد صحیح b1,b2,,bnb_1, b_2, \dots, b_n\, با فاصله از هم داده می‌شود. 1bi1091 \leq b_i \leq 10^9

خروجی🔗

در تنها سطر خروجی، باقی‌مانده‌ی تعداد حالت‌های ممکن برای دنباله‌ی aa را به پیمانه‌ی 109+710^9 + 7 چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

5
2 5 5 3 8
Plain text

خروجی نمونه ۱🔗

4
Plain text

برای مثال اگر آرایه‌ی aa برابر 1,4,2,1,9,\langle 1, 4, 2, -1, 9 \rangle, باشد، دنباله‌ی bbی داده شده، بدست می‌آید (۳ آرایه‌ی اولیه دیگر نیز وجود دارد).

ورودی نمونه ۲🔗

4
2 1 2 1
Plain text

خروجی نمونه ۲🔗

1
Plain text

آرایه‌ی aa فقط می‌تواند 1,0,2,1\langle 1, 0, 2, -1 \rangle باشد.

ورودی نمونه ۳🔗

1
1403
Plain text

خروجی نمونه ۳🔗

0
Plain text

هیچ آرایه‌ی aa با یک عنصر وجود ندارد.