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

---

جایگشتی از اعداد $1$ تا $n$ در اختیار داریم که $n$ عددی زوج است. در هر مرحله مشتلی دو عضو مجاور را انتخاب می‌کند که عضو سمت چپ بزرگتر از عضو سمت راست باشد، سپس هر دو را حذف کرده و باقی اعضای آرایه را به هم می‌چسباند.

حال مشتلی می‌خواهد تعداد روش‌های پاک کردن تمام اعضای جایگشت را پیدا کند. از آن‌جایی که ممکن است این مقدار بیش از حد بزرگ شود، مشتلی از شما می‌خواهد که باقی‌مانده این مقدار بر $10^9+7$ را برای او پیدا کنید.

ورودی

در اولین سطر ورودی، عدد طبیعی زوج $n$ نمایانگر طول جایگشت آمده است. $$2 \le n \le 500$$

در سطر بعد جایگشت $a_1, a_2, ..., a_n,$ آمده است.

خروجی

در تنها سطر خروجی، باقی‌مانده تعداد روش‌های حذف تمام اعضای جایگشت ورودی بر $10^9+7$ را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

6
6 4 3 2 1 5

خروجی نمونه ۱

3

۳ روش حذف تمام اعضا:

• $[6, 4, 3, 2, 1, 5] \rightarrow [6, 2, 1, 5] \rightarrow [6, 5] \rightarrow []$
• $[6, 4, 3, 2, 1, 5] \rightarrow [6, 4, 1, 5] \rightarrow [6, 5] \rightarrow []$
• $[6, 4, 3, 2, 1, 5] \rightarrow [6, 4, 3, 5] \rightarrow [6, 5] \rightarrow []$

ورودی نمونه ۲

8
5 8 6 7 2 3 4 1

خروجی نمونه ۲

9

۹ روش حذف تمام اعضا:

• $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 7, 2, 3, 4, 1] \rightarrow [5, 3, 4, 1] \rightarrow [4, 1] \rightarrow []$
• $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 7, 2, 3, 4, 1] \rightarrow [5, 3, 4, 1] \rightarrow [5, 3] \rightarrow []$
• $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 7, 2, 3, 4, 1] \rightarrow [5, 7, 2, 3] \rightarrow [5, 3] \rightarrow []$
• $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 3, 4, 1] \rightarrow [5, 3, 4, 1] \rightarrow [4, 1] \rightarrow []$
• $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 3, 4, 1] \rightarrow [5, 3, 4, 1] \rightarrow [5, 3] \rightarrow []$
• $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 3, 4, 1] \rightarrow [5, 8, 4, 1] \rightarrow [5, 1] \rightarrow []$
• $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 3, 4, 1] \rightarrow [5, 8, 6, 3] \rightarrow [5, 3] \rightarrow []$
• $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 7, 2, 3] \rightarrow [5, 7, 2, 3] \rightarrow [5, 3] \rightarrow []$
• $[5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 7, 2, 3] \rightarrow [5, 8, 6, 3] \rightarrow [5, 3] \rightarrow []$