Divide the candies

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka has 2 rows with \(n\) candies in each. Marichka numbered the candies in each row. In the first row, the candies are numbered from 1 to \(n\) from left to right. In the second row, the candies are also numbered from 1 to \(n\), the number of each candy is unique, but the order can be arbitrary. That is, in the second row, the numbers form an arbitrary permutation, and in the first — the identity permutation.

After that, Marichka decided to eat all the candies. To do this, she chooses the leftmost candy from the first row or the leftmost candy from the second row (at her choice) and eats it. Marichka continues this until she eats all the candies.

Zenyk knows the sequence of candy numbers in the order Marichka ate them. Now Zenyk is interested in how many different sequences of candy numbers in the second row could have been. Since this number can be large, find its remainder when divided by \(10^9+7\).

Input

The first line contains a single integer \(n\) — the initial number of candies in each row.

The second line contains \(2n\) integers \(a_i\) — the numbers of the candies in the order Marichka ate them.

Output

Print a single number — the number of possible sequences of numbers in the second row modulo \(10^9+7\).

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le a_i \le n\),

Among all \(a_i\), each value from 1 to \(n\) appears exactly 2 times.

Samples