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

پدر حنا برای هدیه تولد او، صندوقچه‌ی پدربزرگش را باز کرده‌است و تکه‌ کد زیر را به او داده‌است. (کد زیر یک شبه‌کد است و می‌توانید درباره شبه‌کد در این‌جا بخوانید.)

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