「MCOI-07」Dream and Discs

**均匀随机** 指对所有可行的结果随机选一个结果，其中所有可行结果等概率被选择。

Dream 有 $n$ 片音乐盘，编号为 $1$ 到 $n$。所有盘都存恰好一首歌，其中编号为 $i$ 的盘所存储歌由正整数 $a_i$ 表示。$a_i$ 满足 $1\le a_i\le n$。 Dream 打算**均匀随机**选择一个编号区间 $P_1$ 和一个歌曲区间 $S_1$，其中 $P_1\subseteq [1,n]$，$S_1\subseteq [1,n]$，并且所有区间端点均为正整数。 Dream 取完两个区间，他会选择尽量多的盘，使得盘编号在 $P_1$ 里，歌曲在 $S_1$ 里，并且所有歌曲互不相同。他准备把这集音乐盘给 Tommy。 Dream 构造完集合发现他选了太多音乐盘，决定由以上选区间方法再次**均匀随机**选取两个区间 $P_2$ 和 $S_2$，其中 $P_2\subseteq P_1$ 并 $S_2\subseteq S_1$。这次，他构造的音乐盘集需要满足编号在 $P_2$ 里，歌曲在 $S_2$ 里。Dream 仍然会选尽量大，歌曲互不相同的集合。 **Dream 永远不会选空区间。** 现在 Tommy 感觉 Dream 给他的音乐盘太少了。请帮 Tommy 计算 Dream 第二次选取 **平均** 导致的集合大小减少量。 这里，平均对所有合法 $(P_1,S_1,P_2,S_2)$ 选取方案等权重平均。

第一行一个正整数 $n$。 第二行 $n$ 个正整数，依次表示 $a_1,a_2,\dots,a_n$。

假设答案可以表示为 $p/q$，其中 $p$ 和 $q$ 互质。请输出 $p\cdot q^{-1}\pmod{10^9+7}$。

2
1 2

920000007

3
1 1 2

480000004

5
1 2 1 3 2

734081639

#### 样例 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$ 总共有 $25$ 方案，所有方案减量之和为 $14$，于是答案等于 $14/25$。 #### 样例 2 解释 答案为 $144/225$。 #### 样例 3 解释 答案为 $5921/4900$。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（11 pts）：$n\le8$。 - Subtask 2（17 pts）：$n\le64$。 - Subtask 3（19 pts）：$n\le1024$。 - Subtask 4（7 pts）：$a_i\le 10$。 - Subtask 5（23 pts）：$n\le10^5$。 - Subtask 6（23 pts）：无特殊限制。 对于所有数据，$1\le n\le5\cdot10^5,1\le a_i\le n$。