P10141 [USACO24JAN] Merging Cells P

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

Bessie 正在玩一个著名的在线游戏，游戏中有许多不同编号和大小的细胞。细胞会被其他细胞吞噬，直到只剩下一个胜利者。 有 $N$（$2\le N\le 5000$）个细胞从左到右排成一行，编号为 $1\ldots N$，初始大小为 $s_1,s_2,\ldots,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

输入的第一行包含 $N$。 第二行包含 $s_1,s_2,\ldots,s_N$。

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

### 样例解释 1 存在两种可能性，其中 $(a,b)\to c$ 表示编号为 $a$ 和 $b$ 的细胞合并成了一个编号为 $c$ 的新的细胞。 $(1, 2) \to 2, (2, 3) \to 2$ $(2, 3) \to 3, (1, 3) \to 3$ 所以有各 $\frac{1}{2}$ 的概率最终的细胞具有编号 $2$ 或 $3$。 ### 样例解释 2 六种可能性如下： $(1, 2) \to 1, (1, 3) \to 1, (1, 4) \to 1$ $(1, 2) \to 1, (3, 4) \to 4, (1, 4) \to 1$ $(2, 3) \to 3, (1, 3) \to 1, (1, 4) \to 1$ $(2, 3) \to 3, (3, 4) \to 3, (1, 3) \to 3$ $(3, 4) \to 4, (2, 4) \to 4, (1, 4) \to 4$ $(3, 4) \to 4, (1, 2) \to 1, (1, 4) \to 1$ 所以有 $\frac{2}{3}$ 的概率最终的细胞具有编号 $1$，各 $\frac{1}{6}$ 的概率最终的细胞具有编号 $3$ 或 $4$。 ### 测试点性质 - 测试点 3：$N\le 8$。 - 测试点 $4-8$：$N\le 100$。 - 测试点 $9-14$：$N\le 500$。 - 测试点 $15-22$：没有额外限制。