← 返回题目列表

AtCoder · summerfes2018_c

C. 整数占卜

中文机器翻译题面 查看原题

配点 : 100 点

問題文

MMNMM决定在夏日祭的摊位上进行兼容性算命。
兼容性算命是使用算命盒和里面写有整数的标签来完成的。
首先,盒子里面是 包含 N 账单, i 番目( 1 \leq i \leq N ) 是一个整数。 写入 a_i 。

参与算命的两人决定一个回合,第一个人从盒子里的牌中随机选择一张牌(这样选择盒子里任何一张牌的可能性是相等的),另一个人以同样的方式选择一张牌,而不把那张牌放回去。
两个人之间的兼容性是由两个人选择的整数决定的,以“相似度(2),兼容性(1),丈夫(2),妻子(2)”命名。 X,Y 按此顺序输出 2+XY+2X+2Y 不过算命之神不能处理大数字,所以实际兼容性是 它是除以 2+XY+2X+2Y 的值,直到 10^9+7 的余数。
检查兼容性后,不要将所选卡放回原处,而是检查兼容性( 返回写有余数(除以 10^9+7 )的卡片。

兼容性算命 N-1 组内参与者的兼容性 求余数的期望值(除以 10^9+7 )。

制約

所有测试用例都满足以下约束。

  • 2 \leq N \leq 10^6
  • 0 \leq a_i < 10^9+6 (i = 1, 2, ..., N)

入力

输入是按以下格式从标准输入给出的。

N
a_1 a_2 ... a_N
  • 第一行包含一个整数 写入 N 。这意味着盒子里首先有钞票。 这表明包含 N 件。
  • 第二行包含一个整数 a_1, a_2, ..., a_N 按此顺序写入,并用空格分隔。这是盒子里最初的钞票之一。 i 枚目 (1 \leq i \leq N) 是 在 a_i 。

出力

到标准输出,到 在一行上打印表示 (除以 N-1 组内参与者的兼容性 求余数的期望值(除以 10^9+7 ) 的期望值的整数。绝对误差 10^{-5} 在以下情况下,答案被确定为正确。


入力例 1

3
1 2 3

出力例 1

58.000000

例如,第一组是 获取 (1, 3) 标签并 插入 2 + 1 \times 3 + 2 \times 1 + 2 \times 3 = 13 钞票,第二套将被 如果您使用 (2, 13) 卡,则第二对的兼容性为 2 + 2 \times 13 + 2 \times 2 + 2 \times 13 = 58 。 这就是答案,因为无法实现大于