+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- افراد ۱ تا $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$