25217번 - W 서브태스크다국어

문제

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₁ p₂ ... p_N) and (q₁ q₂ ... 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.

입력

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

출력

Print a single number: the number of distinct W-shaped permutations, modulo 1,000,000,007.

제한

• 5 ≤ N ≤ 300,000
• Array values are integers between 1 and 1,000,000 inclusive.

서브태스크

힌트