Description

Dream has $n$ music discs, numbered from $1$ to $n$. Each disc stores exactly one song, and the song stored on disc $i$ is represented by a positive integer $a_i$. The values $a_i$ satisfy $1 \le a_i \le n$.

Dream plans to uniformly randomly choose an index interval $P_1$ and a song interval $S_1$, where $P_1 \subseteq [1,n]$, $S_1 \subseteq [1,n]$, and all interval endpoints are positive integers.

After choosing the two intervals, he will select as many discs as possible such that the disc indices are in $P_1$, the songs are in $S_1$, and all chosen songs are pairwise distinct. He plans to give this set of discs to Tommy.

After constructing the set, Dream finds that he selected too many discs. He decides to use the above method to uniformly randomly choose two intervals $P_2$ and $S_2$ again, where $P_2 \subseteq P_1$ and $S_2 \subseteq S_1$. This time, the set of discs he constructs must satisfy that the indices are in $P_2$ and the songs are in $S_2$. Dream still selects a maximum-size set with all songs pairwise distinct.

Dream will never choose an empty interval.

Now Tommy feels that Dream gave him too few discs. Please help Tommy compute the average decrease in the size of the set caused by Dream’s second selection.

Here, the average is taken uniformly over all valid choices of $(P_1, S_1, P_2, S_2)$.

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

Suppose the answer can be written as $p/q$, where $p$ and $q$ are coprime. Output $p \cdot q^{-1} \pmod{10^9+7}$.

2
1 2

920000007

3
1 1 2

480000004

5
1 2 1 3 2

734081639

Hint

Explanation for Sample 1

• $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 $25$ total choices. The sum of decreases over all choices is $14$, so the answer equals $14/25$.

Explanation for Sample 2

The answer is $144/225$.

Explanation for Sample 3

The answer is $5921/4900$.

Constraints

This problem uses bundled testdata.

• 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 special restrictions.

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

Translated by ChatGPT 5