408151: GYM103003 C Discs

Dream stole $$$n$$$ of Tommy's music discs, labeled with positive integers from $$$1$$$ to $$$n$$$. The track in the $$$i$$$-th disc is given by the integer $$$a_i$$$, where $$$1\le a_i\le n$$$.

Dream now wants to return a certain set of discs to Tommy. After deciding upon a set of discs to return, Dream burns the least amount of discs necessary such that the tracks of the remaining discs are distinct. In other words, the amount of discs Tommy receives equals the amount of distinct tracks in the initial set of discs.

Dream randomly chooses eight integers, $$$l_1,l_2,r_2,r_1,L_1,L_2,R_2,R_1$$$, such that $$$1\le l_1\le l_2\le r_2\le r_1\le n$$$ and $$$1\le L_1\le L_2\le R_2\le R_1\le n$$$. He initially decided to return to Tommy all discs that had a label in $$$[l_1,r_1]$$$ and a track in $$$[L_1,R_1]$$$. However, after Tommy was charged with five accounts of arson on the SMP, Dream changed his mind and instead chose to return the discs with a label in $$$[l_2,r_2]$$$ and a track in $$$[L_2,R_2]$$$.

The amount of discs Tommy received decreased by some amount. Calculate this expected decrease modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

The first line contains an integer $$$n$$$, the amount of music discs Dream has ($$$1\le n\le 5\times10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$.

Output one integer, the expected decrease modulo $$$10^9+7$$$.

• In the first subtask, worth $$$11$$$ points, $$$n\le8$$$.
• In the second subtask, worth $$$17$$$ points, $$$n\le64$$$.
• In the third subtask, worth $$$19$$$ points, $$$n\le1024$$$.
• In the fourth subtask, worth $$$7$$$ points, $$$a_i\le 10$$$.
• In the fifth subtask, worth $$$23$$$ points, $$$n\le 10^5$$$.
• In the sixth subtask, worth $$$23$$$ points, no additional constraints are imposed.

2
1 2

920000007

3
1 1 2

480000004

5
1 2 1 3 2

734081639

In the first sample, there are $$$25$$$ possibilities for $$$l_1,l_2,r_2,r_1,L_1,L_2,R_2,R_1$$$, all of which are listed below.

• $$$[l_1,r_1]=[1,1],[L_1,R_1]=[1,1]$$$
  • $$$[l_2,r_2]=[1,1],[L_2,R_2]=[1,1],\Delta=1-1=0$$$

• $$$[l_1,r_1]=[1,1],[L_1,R_1]=[1,2]$$$
  • $$$[l_2,r_2]=[1,1],[L_2,R_2]=[1,1],\Delta=1-1=0$$$
  • $$$[l_2,r_2]=[1,1],[L_2,R_2]=[1,2],\Delta=1-1=0$$$
  • $$$[l_2,r_2]=[1,1],[L_2,R_2]=[2,2],\Delta=1-0=1$$$

• $$$[l_1,r_1]=[1,1],[L_1,R_1]=[2,2]$$$
  • $$$[l_2,r_2]=[1,1],[L_2,R_2]=[2,2],\Delta=0-0=0$$$

• $$$[l_1,r_1]=[1,2],[L_1,R_1]=[1,1]$$$
  • $$$[l_2,r_2]=[1,1],[L_2,R_2]=[1,1],\Delta=1-1=0$$$
  • $$$[l_2,r_2]=[1,2],[L_2,R_2]=[1,1],\Delta=1-1=0$$$
  • $$$[l_2,r_2]=[2,2],[L_2,R_2]=[1,1],\Delta=1-0=1$$$

• $$$[l_1,r_1]=[1,2],[L_1,R_1]=[1,2]$$$
  • $$$[l_2,r_2]=[1,1],[L_2,R_2]=[1,1],\Delta=2-1=1$$$
  • $$$[l_2,r_2]=[1,1],[L_2,R_2]=[1,2],\Delta=2-1=1$$$
  • $$$[l_2,r_2]=[1,1],[L_2,R_2]=[2,2],\Delta=2-0=2$$$
  • $$$[l_2,r_2]=[1,2],[L_2,R_2]=[1,1],\Delta=2-1=1$$$
  • $$$[l_2,r_2]=[1,2],[L_2,R_2]=[1,2],\Delta=2-2=0$$$
  • $$$[l_2,r_2]=[1,2],[L_2,R_2]=[2,2],\Delta=2-1=1$$$
  • $$$[l_2,r_2]=[2,2],[L_2,R_2]=[1,1],\Delta=2-0=2$$$
  • $$$[l_2,r_2]=[2,2],[L_2,R_2]=[1,2],\Delta=2-1=1$$$
  • $$$[l_2,r_2]=[2,2],[L_2,R_2]=[2,2],\Delta=2-1=1$$$

• $$$[l_1,r_1]=[1,2],[L_1,R_1]=[2,2]$$$
  • $$$[l_2,r_2]=[1,1],[L_2,R_2]=[2,2],\Delta=1-0=1$$$
  • $$$[l_2,r_2]=[1,2],[L_2,R_2]=[2,2],\Delta=1-1=0$$$
  • $$$[l_2,r_2]=[2,2],[L_2,R_2]=[2,2],\Delta=1-1=0$$$

• $$$[l_1,r_1]=[2,2],[L_1,R_1]=[1,1]$$$
  • $$$[l_2,r_2]=[2,2],[L_2,R_2]=[1,1],\Delta=0-0=0$$$

• $$$[l_1,r_1]=[2,2],[L_1,R_1]=[1,2]$$$
  • $$$[l_2,r_2]=[2,2],[L_2,R_2]=[1,1],\Delta=1-0=1$$$
  • $$$[l_2,r_2]=[2,2],[L_2,R_2]=[1,2],\Delta=1-1=0$$$
  • $$$[l_2,r_2]=[2,2],[L_2,R_2]=[2,2],\Delta=1-1=0$$$

• $$$[l_1,r_1]=[2,2],[L_1,R_1]=[2,2]$$$
  • $$$[l_2,r_2]=[2,2],[L_2,R_2]=[2,2],\Delta=1-1=0$$$

The cumulative decrease over all possibilities is $$$14$$$. As such, the expected decrease is $$$14/25$$$.

In the second sample, the expected decrease is $$$144/225$$$.

In the third sample, the expected decrease is $$$5291/4900$$$.