题目背景

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

题目描述

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$。