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

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