← 返回题目列表

Codeforces · 850/F

F. 彩虹球

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

你有一袋 n 个不同颜色的球。你有第 i 种颜色的人工智能球。

当袋子中至少有两个不同颜色的球时,执行以下步骤:

- 取出两个随机球,无需一一替换。这些球可能是相同的颜色。
- 将第二个球着色为第一个球的颜色。在此步骤中您不能改变球的顺序。
- 将两个球放回袋子中。
- 所有这些操作都只需要一秒钟。

设 M = 109 + 7。可以证明,停止之前所需的预计时间可以表示为有理数 $$\frac{p}{q}$$,其中 P 和 Q 是互质整数,其中 Q 不能被 M 整除。返回值 $$P \cdot Q^{-1} \mod M$$。

输入

输入的第一行将包含一个整数 n (1 ≤ n ≤ 2 500) - 颜色数。

输入的下一行将包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 105) - 每种颜色的球的数量。

输出

打印一个整数,即问题的答案。

示例

输入 #1

2
1 1

输出 #1

1

输入 #2

3
1 2 3

输出 #2

750000026

注意

在第一个示例中,无论发生什么,一步后球都会变成相同的颜色。

对于第二个样本,我们有 6 个球。让我们将球标记为 1 到 6,不失一般性,假设球 1,2,3 最初是颜色 1,球 4,5 是颜色 2,球 6 是颜色 3。

以下是这些步骤如何进行的示例:

- 我们选择球 5 和球 6。然后球 6 变为颜色 2。
- 我们选择球 4 和球 5。球 5 保持相同的颜色(颜色 2)。
- 我们选择球 1 和球 5。球 5 变为颜色 1。
- 我们选择球 6 和球 5。球 5 变为颜色 2。
- 我们选择球 3 和球 4。球 4 变为颜色 1。
- 我们选择球 4 和球 6。球 6 变为颜色 1。
- 我们选择球 2 和球 5。球 5 变为颜色 1。

可以证明,这种情况的答案是 $${ \frac { 8 3 } { 4 } }$$。