注意：本题内存限制为 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$)。当细胞数量大于 1 时，会随机等概率地选择一对相邻的细胞进行合并，合并规则如下：

如果一个标签为 $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$。

输出格式

对于每个 $i \in \{1, \dots, N\}$，输出最终细胞标签为 $i$ 的概率对 $10^9+7$ 取模的结果，每行一个。

样例

输入格式 1

3
1 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

因此，最终细胞标签为 2 或 3 的概率均为 $1/2$。

输入格式 2

4
3 1 1 1

输出格式 2

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

因此，最终细胞标签为 1 的概率为 $2/3$，标签为 3 或 4 的概率均为 $1/6$。

子任务

• 输入 3：$N\le 8$
• 输入 4-8：$N\le 100$
• 输入 9-14：$N\le 500$
• 输入 15-22：无额外限制。