题目描述

题目来自 USACO 2024 January Contest, Platinum Problem 2. Merging Cells

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 < c_b \ \max(a, b) & c_a = c_b \end{cases} ]

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

输入格式

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

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

输出格式

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

样例 1

输入

3
1 1 1

输出

0
500000004
500000004

样例说明

存在两种可能性，其中 $(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

输入

4
3 1 1 1

输出

666666672
0
166666668
166666668

样例说明

六种可能性如下：

1. $(1, 2) \to 1$，$(1, 3) \to 1$，$(1, 4) \to 1$
2. $(1, 2) \to 1$，$(3, 4) \to 4$，$(1, 4) \to 1$
3. $(2, 3) \to 3$，$(1, 3) \to 1$，$(1, 4) \to 1$
4. $(2, 3) \to 3$，$(3, 4) \to 3$，$(1, 3) \to 3$
5. $(3, 4) \to 4$，$(2, 4) \to 4$，$(1, 4) \to 4$
6. $(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	没有额外限制