+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
پدر حنا برای هدیه تولد او، صندوقچه‌ی پدربزرگش را باز کرده‌است و تکه کد زیر را به او داده‌است. (کد زیر یک شبه‌کد است و می‌توانید درباره شبه‌کد در [این‌جا](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
```