Gomory, Hu și pietricelele colorate

Gomory and Hu found $n$ pebbles near the lake. They noticed that they are very colorful. They want to arrange them in a sequence ... $with\ their\ eyes\ closed$. Due to the large number of possible arrangements, they ask for your help in computing the average number of maximal sequences of stones of the same color resulting from an arrangement, considering all possible arrangements to be equally likely.

Task

Formally, you are given an array $C$ of length $n$ with elements between $1$ and $n$. You must compute the average number of maximal sequences with equal values for a random permutation of the array modulo $10^9 + 7$.

Input Data

On the first line, a natural number $n$ is read, representing the length of the array.

On the second line, $n$ natural numbers separated by spaces are read, representing the elements of the array $C$.

Output Data

On the first line you must output a single natural number representing the average number of maximal contiguous sequences with equal elements of a permutation of the array $C$. It can be shown that the answer can be written as an irreducible fraction $\frac{a}{b}$, where $a$ and $b$ are natural numbers and $b \not\equiv 0 \pmod{10^9 + 7}$. You must output $a\cdot b^{-1}$ modulo $10^9 + 7$.

Constraints

• $1 \le n \le 10^6$
• $1 \le C_i \le n$
• A sequence is obtained from an array by removing a number of elements from the beginning of the array (possibly zero) and a number of elements from the end of the array (possibly zero).
• A maximal sequence with equal elements is a sequence of equal elements that can no longer be extended to the right or to the left while still being made up of the same element.
• Two permutations are considered different if they differ in at least one position. For example, the array $[1 , 2 , 2]$ has only $3$ permutations: $[1 , 2 , 2]$, $[2 , 1 , 2]$, $[2 , 2 , 1]$.

Example 1

stdin

2
1 2

stdout

2

Explanation

The permutations of the array are: $[1 , 2]$ and $[2 , 1]$. Each of them has $2$ maximal contiguous sequences with equal values. Therefore, the average value is $2$.

Example 2

stdin

3
2 1 2

stdout

333333338

Explanation

The permutations of the array are: $[1 , 2 , 2]$, $[2 , 1 , 2]$ and $[2 , 2 , 1]$. These have $2$, $3$, and respectively $2$ maximal sequences with equal elements. The average number of maximal sequences with equal elements is $\frac{2 + 3 + 2}{3}\ =\ \frac{7}{3}\ =\ 333333338\ (modulo\ 10^9+7)$.