[ABC352] G - Socks 3

G - Socks 3

Time Limit: 3 sec / Memory Limit: 1024 MB

分数: 600 分

题面

高桥的抽屉里有各种颜色的袜子。袜子的颜色由 到 的整数表示，每种颜色的袜子数量为 。

他将通过执行以下操作来选择今天要穿的袜子：

• 不断地从抽屉里随机抽取一只袜子，直到他已经抽过的袜子中可以凑成一双相同颜色的袜子为止。一旦抽取了一只袜子，就不会再放回抽屉。

求他需要从抽屉中抽出袜子的次数的期望值，对 取模后的结果。

找到期望值对 取模的含义是什么呢？可以证明所求期望值总是有理数。此外，该问题的限制条件保证，如果期望值可以表示为既约分数 ，则 不可被 整除。在这里，存在一个唯一的整数 ，满足 ，且 介于 和 之间。找到这个 。

限制条件

• 所有输入值均为整数。

---

输入

从标准输入中以以下格式给出输入：

输出

输出答案。

---

输入样例 1

2
2 2

输出样例 1

665496238

例如，该操作可以按以下方式执行：

1. 从抽屉中抽取一只颜色为 的袜子。抽屉中剩下颜色为 的一只袜子和颜色为 的两只袜子。
2. 从抽屉中抽取一只颜色为 的袜子。抽屉中剩下颜色为 和 各一只袜子。
3. 从抽屉中抽取一只颜色为 的袜子。目前已经抽取的袜子有两只颜色为 和一只颜色为 的袜子，可以凑成一双颜色为 的袜子，结束操作。

在这个例子中，高桥从抽屉中抽出袜子共三次。

高桥从抽屉中抽取袜子的次数的期望值为 的概率为 ，为 的概率为 ，因此期望值为 。

---

输入样例 2

1
352

输出样例 2

2

---

输入样例 3

6
1796 905 2768 253 2713 1448

输出样例 3

887165507