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

---

افراد ۱ تا \(n\) تیم‌بندی شده‌اند و در یک صف قرار گرفته‌اند. به یک شیوه تیم بندی یک دنباله \(a_1,a_2,...,a_n\) نسبت میدهیم به این شکل که به ترتیب عناصر دنباله را میسازیم:

• در مرحله \(i\) ام اگر فرد با شماره \(i\) با فرد شماره \(j\) هم‌تیمی بود به شکلی که \(i>j\) \(a_i\) را برابر \(a_j\) قرار میدهیم.
• در غیر این صورت \(a_i\) را برابر مینیمم عدد طبیعی مانند \(x\) قرار می‌دهیم که \(x\) برابر هیچ کدام از اعداد \(a_1,a_2,...,a_{i-1}\) نباشد.

یک دنباله \(a_1,a_2,...,a_n\) به شما داده شده است که تضمین می‌شود تیم‌بندی‌ای وجود داره که دنباله‌اش برابر آن شود. تعداد تیم‌بندی‌‌هایی را بشمارید که دنباله‌هایشان از لحاظ لکسیکوگرافیکالی کمتر یا برابر دنباله \(a\) باشد. چون ممکن است این عدد خیلی بزرگ باشد، باقی‌مانده آن را به \(1\ 000\ 007\) حساب کنید.

ورودی

در خط اول ورودی یک عدد \(n\) داده شده است. در خط دوم دنباله \(a_1,a_2,...,a_n\) داده شده است. \[1 \leq n \leq 10\ 000\]

خروجی

باقی‌مانده تعداد تیم‌بندی‌های با شرایط گفته شده بر \(1\ 000\ 007\) را در یک خط چاپ کنید.

زیر مسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۳۰	\[n \le 14\]
۲	۲۰	\[n \le 100\]
۳	۲۰	\[n \le 1\ 000\]
۴	۳۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

3
1 2 2

خروجی نمونه ۱

4

دنباله‌های معتبر:

• \(1 1 1\)
• \(1 1 2\)
• \(1 2 1\)
• \(1 2 2\)
• \(1 2 3\)