Problem Background

Note: The memory limit for this problem is 512MB, twice the usual limit.

Problem Description

Bessie is playing a famous online game where there are many cells with different numbers and sizes. Cells will be absorbed by other cells until only one remains as the winner.

There are $N$ ($2 \le N \le 5000$) cells arranged in a row from left to right, numbered $1 \ldots N$, with initial sizes $s_1, s_2, \ldots, s_N$ ($1 \le s_i \le 10^5$). When there are multiple cells, a pair of adjacent cells is chosen uniformly at random to merge according to the following rules:

If a cell numbered $a$ with current size $c_a$ merges with a cell numbered $b$ with current size $c_b$, the resulting cell's size will be $c_a + c_b$, and its number will be the number of the larger cell, or the larger number if they are equal. Formally, the resulting cell's number will be:
\[ \begin{cases} a & \text{if } c_a > c_b \\ b & \text{if } c_a < c_b \\ \max(a, b) & \text{if } c_a = c_b \end{cases} \]

For each number $i$ in the range $1 \ldots N$, the probability that the final cell has number $i$ can be expressed as $\frac{a_i}{b_i}$, where $b_i \not \equiv 0 \pmod{10^9+7}$. Output $a_i b_i^{-1} \pmod{10^9+7}$.

Input Format

The first line of input contains $N$.

The second line contains $s_1, s_2, \ldots, s_N$.

Output Format

For each $i$ in the range $1 \ldots N$, output a line containing the remainder of the probability that the final cell has number $i$ modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3
1 1 1

Sample Output #1

0
500000004
500000004

Sample Input #2

4
3 1 1 1

Sample Output #2

666666672
0
166666668
166666668

Notes/Hints

Sample Explanation 1

There are two possible scenarios where $(a, b) \to c$ indicates that cells numbered $a$ and $b$ merge into a new cell numbered $c$.

$(1, 2) \to 2, (2, 3) \to 2$
$(2, 3) \to 3, (1, 3) \to 3$

Thus, there is an equal probability ($\frac{1}{2}$) that the final cell has number $2$ or $3$.

Sample Explanation 2

There are six possible scenarios:

$(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$

Thus, there is a $\frac{2}{3}$ probability that the final cell has number $1$, and a $\frac{1}{6}$ probability for each of numbers $3$ or $4$.

Test Case Properties

• Test case 3: $N \le 8$.
• Test cases 4-8: $N \le 100$.
• Test cases 9-14: $N \le 500$.
• Test cases 15-22: No additional restrictions.

见题面 Input 部分

见题面 Output 部分