W

Task

An array of numbers is said to be W-shaped if it meets the following conditions:

1. It consists of four segments in decreasing order, increasing order, decreasing order, increasing order.
2. The ordering is not strict, so increasing and decreasing segments may include consecutive equal elements.
3. Every two consecutive segments have a common endpoint.
4. Every segment contains at least two distinct values.

For example, the array $(3 \ 1 \ 2 \ 1 \ 1 \ 4)$ is W-shaped, since it consists of the segments $(3, 1), (1 \ 2), (2 \ 1 \ 1), (1 \ 4)$. The array $(3 \ 1 \ 2 \ 2 \ 2 \ 4)$ is not W-shaped. It could be broken into the segments $(3 \ 1), (1 \ 2), (2 \ 2 \ 2), (2 \ 4)$, however the segment $(2 \ 2 \ 2)$ does not contain two distinct values.

Given an array of $N$ integers, how many distinct permutations of the array are W-shaped? Two permutations of the array, $(p_1 \ p_2 \dots p_N)$ and $(q_1 \ q_2 \dots q_N)$, are considered distinct if there exists a position $1 ≤ i ≤ N$ where $p_i ≠ q_i$. In the example above, $(3 \ 1 \ 2 \ 1 \ 1 \ 4)$ should only be counted once, because permuting the three $1$’s does not create distinct permutations.

Input data

The first line contains $N$. The second line contains the $N$ values of the array, separated by spaces.

Output data

Print a single number: the number of distinct W-shaped permutations, modulo $10^9 + 7$.

Constraints and clarifications

• $5 \leq N \leq 300 \ 000$
• Array values are integers between $1$ and $1 \ 000 \ 000$ inclusive.
• Test cases will be scored individually.

Example 1

stdin

5
3 1 4 2 3

stdout

6

Explanation

The six distinct W-shaped permutations are:

• $3 \ 1 \ 3 \ 2 \ 4$
• $3 \ 1 \ 4 \ 2 \ 3$
• $3 \ 2 \ 3 \ 1 \ 4$
• $3 \ 2 \ 4 \ 1 \ 3$
• $4 \ 1 \ 3 \ 2 \ 3$
• $4 \ 2 \ 3 \ 1 \ 3$

Example 2

stdin

7
1 2 2 2 3 4 4

stdout

72