Problem Background

Uniformly Random refers to selecting one outcome from all feasible results, where all feasible results are equally likely to be chosen.

Problem Description

Dream has $n$ music discs, numbered from $1$ to $n$. Each disc stores exactly one song, represented by a positive integer $a_i$ where $1 \le a_i \le n$. Dream plans to uniformly randomly select a number interval $P_1$ and a song interval $S_1$, where $P_1 \subseteq [1, n]$ and $S_1 \subseteq [1, n]$, and all interval endpoints are positive integers.
After selecting the two intervals, Dream will choose as many discs as possible such that the disc numbers are within $P_1$, the songs are within $S_1$, and all songs are distinct. He intends to give this set of music discs to Tommy.
Dream realizes he has selected too many music discs and decides to uniformly randomly select two new intervals $P_2$ and $S_2$, where $P_2 \subseteq P_1$ and $S_2 \subseteq S_1$. This time, the set of music discs must satisfy the numbers within $P_2$ and the songs within $S_2$. Dream will still choose the largest possible set with distinct songs.
Dream will never select empty intervals.
Now, Tommy feels that the number of music discs given by Dream is too small. Please help Tommy calculate the average reduction in the size of the set caused by Dream's second selection.
Here, the average is taken over all valid $(P_1, S_1, P_2, S_2)$ selection schemes with equal weight.

Input Format

The first line contains a positive integer $n$.
The second line contains $n$ positive integers, representing $a_1, a_2, \dots, a_n$ in order.

Output Format

Assume the answer can be expressed as $p/q$, where $p$ and $q$ are coprime. Please output $p \cdot q^{-1} \pmod{10^9+7}$.

Sample Input and Output

Sample Input #1

2
1 2

Sample Output #1

920000007

Sample Input #2

3
1 1 2

Sample Output #2

480000004

Sample Input #3

5
1 2 1 3 2

Sample Output #3

734081639

Notes

Sample 1 Explanation

• $P_1=[1,1], S_1=[1,1]$
• $P_2=[1,1], S_2=[1,1], \Delta=1-1=0$
• $P_1=[1,1], S_1=[1,2]$
• $P_2=[1,1], S_2=[1,1], \Delta=1-1=0$
• $P_2=[1,1], S_2=[1,2], \Delta=1-1=0$
• $P_2=[1,1], S_2=[2,2], \Delta=1-0=1$
• $P_1=[1,1], S_1=[2,2]$
• $P_2=[1,1], S_2=[2,2], \Delta=0-0=0$
• $P_1=[1,2], S_1=[1,1]$
• $P_2=[1,1], S_2=[1,1], \Delta=1-1=0$
• $P_2=[1,2], S_2=[1,1], \Delta=1-1=0$
• $P_2=[2,2], S_2=[1,1], \Delta=1-0=1$
• $P_1=[1,2], S_1=[1,2]$
• $P_2=[1,1], S_2=[1,1], \Delta=2-1=1$
• $P_2=[1,1], S_2=[1,2], \Delta=2-1=1$
• $P_2=[1,1], S_2=[2,2], \Delta=2-0=2$
• $P_2=[1,2], S_2=[1,1], \Delta=2-1=1$
• $P_2=[1,2], S_2=[1,2], \Delta=2-2=0$
• $P_2=[1,2], S_2=[2,2], \Delta=2-1=1$
• $P_2=[2,2], S_2=[1,1], \Delta=2-0=2$
• $P_2=[2,2], S_2=[1,2], \Delta=2-1=1$
• $P_2=[2,2], S_2=[2,2], \Delta=2-1=1$
• $P_1=[1,2], S_1=[2,2]$
• $P_2=[1,1], S_2=[2,2], \Delta=1-0=1$
• $P_2=[1,2], S_2=[2,2], \Delta=1-1=0$
• $P_2=[2,2], S_2=[2,2], \Delta=1-1=0$
• $P_1=[2,2], S_1=[1,1]$
• $P_2=[2,2], S_2=[1,1], \Delta=0-0=0$
• $P_1=[2,2], S_1=[1,2]$
• $P_2=[2,2], S_2=[1,1], \Delta=1-0=1$
• $P_2=[2,2], S_2=[1,2], \Delta=1-1=0$
• $P_2=[2,2], S_2=[2,2], \Delta=1-1=0$
• $P_1=[2,2], S_1=[2,2]$
• $P_2=[2,2], S_2=[2,2], \Delta=1-1=0$

There are a total of $25$ schemes, with the sum of reductions being $14$, so the answer is $14/25$.

Sample 2 Explanation

The answer is $144/225$.

Sample 3 Explanation

The answer is $5921/4900$.

Data Size and Constraints

This problem uses batched testing.

• Subtask 1 (11 pts): $n \le 8$.
• Subtask 2 (17 pts): $n \le 64$.
• Subtask 3 (19 pts): $n \le 1024$.
• Subtask 4 (7 pts): $a_i \le 10$.
• Subtask 5 (23 pts): $n \le 10^5$.
• Subtask 6 (23 pts): No additional constraints.

For all data, $1 \le n \le 5 \cdot 10^5, 1 \le a_i \le n$.

见题面 Input 部分

见题面 Output 部分