حذف نابه‌جایی


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

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

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

ورودی🔗

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

در سطر بعد جایگشت a1,a2,...,ana_1, a_2, ..., a_n\, آمده است.

خروجی🔗

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

مثال‌ها🔗

ورودی نمونه ۱🔗

6
6 4 3 2 1 5
Plain text

خروجی نمونه ۱🔗

3
Plain text

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

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

ورودی نمونه ۲🔗

8
5 8 6 7 2 3 4 1
Plain text

خروجی نمونه ۲🔗

9
Plain text

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

  • [5,8,6,7,2,3,4,1][5,7,2,3,4,1][5,3,4,1][4,1][][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][5,7,2,3,4,1][5,3,4,1][5,3][][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][5,7,2,3,4,1][5,7,2,3][5,3][][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][5,8,6,3,4,1][5,3,4,1][4,1][][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][5,8,6,3,4,1][5,3,4,1][5,3][][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][5,8,6,3,4,1][5,8,4,1][5,1][][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][5,8,6,3,4,1][5,8,6,3][5,3][][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][5,8,6,7,2,3][5,7,2,3][5,3][][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][5,8,6,7,2,3][5,8,6,3][5,3][][5, 8, 6, 7, 2, 3, 4, 1] \rightarrow [5, 8, 6, 7, 2, 3] \rightarrow [5, 8, 6, 3] \rightarrow [5, 3] \rightarrow []