Problem 2. Merging Cells

USACO 2024 January Contest, Platinum

注意：本题的内存限制为 512MB，通常限制的两倍。

Bessie 正在玩一个著名的在线游戏，游戏中有许多不同编号和大小的细胞。细胞会被其他细胞吞噬，直到只剩下一个胜利者。

有 $N$（$2\le N\le 5000$）个细胞从左到右排成一行，编号为 $1\dots N$，初始大小为 $s_1,s_2,\dots,s_N$（$1\le s_i\le 10^5$）。当存在多个细胞时，均匀地随机选择一对相邻细胞，并根据以下规则合并为一个新的细胞：

如果编号为 $a$ 且当前大小为 $c_a$ 的细胞与编号为 $b$ 且当前大小为 $c_b$ 的细胞合并，则合并成的细胞的大小为 $c_a+c_b$，且编号等于较大细胞的编号，并列时则为编号较大的细胞的编号。形式化地说，合并成的细胞的编号为 $\begin{cases} a & c_a > c_b \\ b & c_a < c_b \\ \max(a,b) & c_a = c_b \end{cases}$。

对于 $1\dots N$ 范围内的每个编号 $i$，最终的细胞具有编号 $i$ 的概率可以以 $\frac{a_i}{b_i}$ 的形式表示，其中 $b_i\not\equiv 0 \pmod{10^9+7}$。输出 $a_ib_i^{-1}\pmod{10^9+7}$。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$。

第二行包含 $s_1,s_2,\dots, s_N$。

输出格式（输出至终端 / 标准输出）：

对于 $1\dots N$ 内的每个 $i$ 输出一行，为输出最终的细胞具有编号 $i$ 的概率模 $10^9+7$ 的余数。

输入样例：

3
1 1 1

输出样例：

0
500000004
500000004

存在两种可能性，其中 $(a,b)\to c$ 表示编号为 $a$ 和 $b$ 的细胞合并成了一个编号为 $c$ 的新的细胞。

(1, 2) -> 2, (2, 3) -> 2
(2, 3) -> 3, (1, 3) -> 3

所以有各 $1/2$ 的概率最终的细胞具有编号 2 或 3。

输入样例：

4
3 1 1 1

输出样例：

666666672
0
166666668
166666668

六种可能性如下：

(1, 2) -> 1, (1, 3) -> 1, (1, 4) -> 1
(1, 2) -> 1, (3, 4) -> 4, (1, 4) -> 1
(2, 3) -> 3, (1, 3) -> 1, (1, 4) -> 1
(2, 3) -> 3, (3, 4) -> 3, (1, 3) -> 3
(3, 4) -> 4, (2, 4) -> 4, (1, 4) -> 4
(3, 4) -> 4, (1, 2) -> 1, (1, 4) -> 1

所以有 $2/3$ 的概率最终的细胞具有编号 1，各 $1/6$ 的概率最终的细胞具有编号 3 或 4。

测试点性质： 测试点 3：$N\le 8$。测试点 4-8：$N\le 100$。测试点 9-14：$N\le 500$。测试点 15-22：没有额外限制。

供题：Benjamin Qi