فرض کنید یک ترتیب از اعداد ‎$1$‎ تا ‎$n$‎ به ما داده شده است. درخت دودویی متناظر با این ترتیب برابر است با درخت دودویی که اعداد به ترتیب داده شده در آن درج شده باشند.

برای مثال درخت متناظر با ترتیب ‎$<2,1,3,4>$‎ به صورت زیر ساخته می‌شوند: ‎

• در ابتدا ‎$2$‎ در یک درخت خالی درج می‌شود‎.
• عدد $1$‎ در درخت درج می‌شود و در جای فرزند سمت‌چپ ‎$2$ قرار می‌گیرد.
• عدد $3$‎ در درخت درج می‌شود و در جای فرزند سمت‌راست ‎$2$ قرار می‌گیرد.
• عدد $4$‎ در درخت درج می‌شود و در جای فرزند سمت‌راست ‎$3$‎ قرار می‌گیرد.

به شما یک ترتیب از اعداد ‎$1$‎ تا ‎$n$‎ داده شده است‌، شما باید تعداد ترتیب‌هایی از اعداد یک تا ‎$n$‎ را به‌دست آورید که درخت متناظر با آن‌ها با درخت متناظر با ترتیب داده شده برابر است.‎

• در سطر اول ورودی ‎$1 \leq n \leq 100$‎ آمده است.
• در سطر بعدی ‎$n$‎ عدد متفاوت آمده است که همه‌ی آن‌ها بین ‎$1$‎ تا ‎$n$‎اند.‎

در تنها سطر خروجی جواب سوال را چاپ کنید ، دقت کنید که این عدد امکان دارد از ‎$2^{64}$‎ بیش‌تر شود.

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

• سوال بعد
• سوال قبل