Online Cell Merging Game

Bessie is playing a famous online game involving merging cells. Initially, there are (N) cells arranged in a line with indices (1,2,\dots,N) and sizes (s_1,s_2,\dots,s_N). In each move, while there is more than one cell, a pair of adjacent cells is chosen uniformly at random and merged into a new cell. When two cells with current sizes (c_a) (cell with index (a)) and (c_b) (cell with index (b)) merge, the new cell’s size is (c_a+c_b) and its index is determined as follows: [ \text{new index} = \begin{cases} a, & c_a>c_b,\ b, & c_a<c_b,\ \max(a,b), & c_a=c_b. \end{cases} ] This process is repeated until only one cell remains. For each index (i) ((1\le i\le N)), let the probability that the final surviving cell has index (i) be expressed as a reduced fraction (\frac{a_i}{b_i}) (with (b_i \not\equiv 0 \pmod{10^9+7})). You are to compute (a_i \cdot b_i^{-1} \pmod{10^9+7}) for every (i).

Note that even though the merging order is random, due to the merging rule the final outcome may depend on the order. In fact, every possible full binary tree (consistent with the merge of adjacent segments) represents a distinct outcome. In a full binary tree of (N) leaves the total number of trees is the ((N-1))th Catalan number. The final probability of index (i) is the sum over all trees that yield the final cell with index (i) divided by the total number of trees.

inputFormat

The first line contains a single integer (N) ((2 \le N \le 5000)). The second line contains (N) space‐separated integers (s_1,s_2,\dots,s_N) ((1\le s_i\le 10^5)).

outputFormat

Output (N) space‐separated integers. The (i)th integer is the value of (a_i \cdot b_i^{-1} \pmod{10^9+7}) — the probability that the final surviving cell has index (i).

sample

2
1 2

0 1