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

افراد ۱ تا $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$ را در یک خط چاپ کنید.

زیر مسئله‌ها

مثال

ورودی نمونه ۱

3
1 2 2

خروجی نمونه ۱

4

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

• $1 1 1$
• $1 1 2$
• $1 2 1$
• $1 2 2$
• $1 2 3$