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

---

علی همیشه آرایه‌هایش را گم می‌کند. به همین منظور از روی آرایه‌ها برای خودش یک آرایه‌ی دیگر می‌سازد. به طور دقیق‌تر آرایه‌ای از اعداد صحیح مثل \(a_1, a_2, \dots, a_n\,\) را در نظر بگیرید. از روی آن آرایه‌ی \(b_1, b_2, \dots, b_n\,\) را می‌سازد. به این صورت که برای هر \(i\) از ۱ تا \(n\) مقدار \(b_i\) از رابطه‌ی زیر بدست می‌آید.

\[b_i = \max\{a_1, …, a_i\} + \min\{a_1, …, a_i\}\]

حال علی پیش از اینکه دنبال آرایه‌ی \(a_1, a_2, \dots, a_n\,\) بگردد، می‌خواهد از روی آرایه‌ی \(b_1, b_2, \dots, b_n\,\) بررسی کند چند حالت برای آرایه‌ی اولیه وجود دارد.

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

ورودی

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

در سطر دوم ورودی، \(n\) عدد صحیح \(b_1, b_2, \dots, b_n\,\) با فاصله از هم داده می‌شود. \[1 \leq b_i \leq 10^9\]

خروجی

در تنها سطر خروجی، باقی‌مانده‌ی تعداد حالت‌های ممکن برای دنباله‌ی \(a\) را به پیمانه‌ی \(10^9 + 7\) چاپ کنید.

مثال‌ها

ورودی نمونه ۱

5
2 5 5 3 8

خروجی نمونه ۱

4

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

ورودی نمونه ۲

4
2 1 2 1

خروجی نمونه ۲

1

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

ورودی نمونه ۳

1
1403

خروجی نمونه ۳

0

هیچ آرایه‌ی \(a\) با یک عنصر وجود ندارد.