Розділи цукерки

Limits: 2 sec., 256 MiB

У Марічки є 2 ряди по $n$ цукерок у кожному. Марічка пронумерувала цукерки у кожному ряді. У першому ряду цукерки пронумеровані від 1 до $n$ зліва направо. У другому ряду цукерки теж пронумеровані від 1 до $n$, номер кожної цукерки унікальний, але порядок може бути довільним. Тобто у другому ряду номери утворюють довільну перестановку, а в першому — тотожну.

Після цього Марічка вирішила з’їсти усі цукерки. Для цього вона обирає найлiвiшу цукерку з першого ряду або найлiвiшу цукерку з другого ряду (на її вибiр) i з’їдає її. Так Марiчка продовжує поки не з’їсть усi цукерки.

Зеник знає послідовність номерів цукерок у тому порядку, в якому їх їла Марічка. Тепер Зенику цікаво, скільки різних послідовностей номерів цукерок у другому ряду могло бути. Оскільки це число може бути великим, знайдіть його остачу від ділення на $10^9+7$.

Input

У першому рядку задано одне ціле число $n$ — початкова кількість цукерок у кожному ряді.

У другому рядку задано $2n$ цілих чисел $a_i$ — номери цукерок у тому порядку, у якому їх їла Марічка.

Output

Виведіть єдине число — кількість можливих послідовностей номерів у другому ряду по модулю $10^9+7$.

Constraints

$1 \le n \le 2 \cdot 10^5$,

$1 \le a_i \le n$,

Серед усіх $a_i$ кожне значення від 1 до $n$ зустрічається рівно 2 рази.

Samples