Merging Cells

문제

Bessie is having fun playing a famous online game, where there are a bunch of cells of different labels and sizes. Cells get eaten by other cells until only one winner remains.

There are $NN$ ($2\le N\le 50002\backslash le\; N\backslash le\; 5000$) cells in a row labeled $1\dots N1\backslash dots\; N$ from left to right, with initial sizes $s_1,s_2,\dots ,s_{N}s\_1,s\_2,\backslash dots,s\_N$ ($1\le s_i\le {10}^{5}1\backslash le\; s\_i\backslash le\; 10^5$). While there is more than one cell, a pair of adjacent cells is selected uniformly at random and merged into a single new cell according to the following rule:

If a cell with label $aa$ and current size $c_{a}c\_a$ is merged with a cell with label $bb$ and current size $c_{b}c\_b$, the resulting cell has size $c_a+c_{b}c\_a+c\_b$ and label equal to that of the larger cell, breaking ties by larger label. Formally, the label of the resulting cell is

For each label $ii$ in the range $1\dots N1\backslash dots\; N$, the probability that the final cell has label $ii$ can be expressed in the form $\frac{a_i}{b_i}\backslash frac\{a\_i\}\{b\_i\}$ where $b_i\equiv ̸0(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)b\_i\backslash not\backslash equiv\; 0\backslash pmod\{10^9+7\}$. Output $a_i{b}_i^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7)a\_ib\_i^\{-1\}\backslash pmod\{10^9+7\}$.

입력

The first line contains $NN$.

The next line contains $s_1,s_2,\dots ,s_{N}s\_1,s\_2,\backslash dots,\; s\_N$.

출력

The probability of the final cell having label $ii$ modulo ${10}^9+710^9+7$ for each $ii$ in $1\dots N1\backslash dots\; N$ on separate lines.

3
1 1 1

0
500000004
500000004

4
3 1 1 1

666666672
0
166666668
166666668