Merging Cells

Bessie is playing an online game with a row of cells. Each cell has a label and a size. Cells keep eating their neighbors until only one winner remains.

There are $N$ cells ($2\le N\le 5000$) in a row, labeled $1$ to $N$ from left to right. The initial sizes are $s_1, s_2, \dots, s_N$ ($1\le s_i\le 10^5$).

While more than one cell remains, a pair of adjacent cells is picked uniformly at random and merged into one new cell. Suppose a cell with label $a$ and current size $c_a$ merges with a cell with label $b$ and current size $c_b$. The new cell has size $c_a+c_b$. Its label is the label of the larger cell. If the sizes are equal, the larger label wins. Formally,

$\text{resulting label} = \begin{cases} a & c_a > c_b \\ b & c_a < c_b \\ \max(a,b) & c_a = c_b \end{cases}$

For each label $i$ from $1$ to $N$, find the probability that the final cell has label $i$. The probability can be written as $\frac{a_i}{b_i}$ with $b_i\not\equiv 0 \pmod{10^9+7}$. Print $a_i b_i^{-1} \bmod (10^9+7)$.

The first line contains $N$.

The next line contains $s_1, s_2, \dots, s_N$.

For each label $i$ from $1$ to $N$, print on its own line the probability that the final cell has label $i$, modulo $10^9+7$.