+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پدر حنا برای هدیه تولد او، صندوقچه‌ی پدربزرگش را باز کرده‌است و تکه‌ کد زیر را به او داده‌است. (کد زیر یک شبه‌کد است و می‌توانید درباره شبه‌کد در [این‌جا](https://fa.wikipedia.org/wiki/%D8%B4%D8%A8%D9%87%E2%80%8C%DA%A9%D8%AF) بخوانید.) ``` procedure old_little_code() p := the input array of size n s := an empty stack a := an array of size 2n counter = 1 for i = 1 to n inclusive do: while s is not empty and p[s.top] < p[i] do: a[counter] = s.top counter += 1 s.pop() end while s.push(i) a[counter] = s.top counter += 1 end for while s is not empty do: a[counter] = s.top counter += 1 s.pop() end while return a end procedure ``` در کنار این تکه‌ کد، کاغذی پیدا کرده و آن را نیز به حنا می‌دهد. روی کاغذ نوشته شده "به این تکه کد یک جایگشت از اعداد $1$ تا $n$ را دادم و در خروجی اعداد $a_1, a_2, \ldots, a_{2n}\ $ را گرفتم.". حنا قصد دارد جایگشتی که پدربزرگش به عنوان ورودی به تکه کد داده‌ بود را پیدا کند. به او کمک کنید تا تعداد جایگشت‌های مختلفی که می‌توانند جایگشت پدربزرگش باشند را پیدا کند. # ورودی در سطر اول عدد $n$ آمده‌است. در سطر بعدی، اعداد $a_1, a_2, \ldots, a_{2n}$ به ترتیب آمده‌اند. تضمین می‌شود که به ازای حداقل یک جایگشت، خروجی داده‌شده تولید می‌شود. $$ 1 \leq n \leq 200 \, 000 $$ $$ 1 \leq a_i \leq n $$ # خروجی در تنها سطر خروجی، باقی‌مانده‌ی تعداد جایگشت‌ها بر $10^9 + 7$ را چاپ کنید. # مثال # ورودی نمونه ۱ ``` 2 1 2 2 1 ``` # خروجی نمونه ۱ ``` 1 ``` جایگشت پدربزرگ فقط می‌تواند $\{2, 1\}$ باشد. # ورودی نمونه ۲ ``` 3 1 2 3 3 2 1 ``` # خروجی نمونه ۲ ``` 1 ``` جایگشت پدربزرگ فقط می‌تواند $\{3, 2, 1\}$ باشد. # ورودی نمونه ۳ ``` 4 1 2 2 3 3 1 4 4 ``` # خروجی نمونه ۳ ``` 1 ``` جایگشت پدربزرگ فقط می‌تواند $\{3, 1, 2, 4\}$ باشد. # ورودی نمونه ۴ ``` 5 1 2 2 3 3 4 5 5 4 1 ``` # خروجی نمونه ۴ ``` 3 ```

حل سؤال در بانک سؤالات