Merging Cells

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

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 $N$ ($2\le N\le 5000$) cells in a row labeled $1\dots N$ from left to right, with initial sizes $s_1,s_2,\dots ,s_N$ ($1\le s_i\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 $a$ and current size $c_a$ is merged with a cell with label $b$ and current size $c_b$, the resulting cell has size $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 $\{\begin{array}{ll}a& c_a>c_b\\ b& c_a<c_b\\ \max (a,b)& c_a=c_b\end{array}.$

For each label $i$ in the range $1\dots N$, the probability that the final cell has label $i$ can be expressed in the form $\frac{a_i}{b_i}$ where $b_i\not\equiv 0(\mathrm{mod}10^9+7)$. Output $a_i{b}_i^{-1}(\mathrm{mod}10^9+7)$.

There are two possibilities, where $(a,b)\to c$ means that the cells with labels $a$ and $b$ merge into a new cell with label $c$.

(1, 2) -> 2, (2, 3) -> 2
(2, 3) -> 3, (1, 3) -> 3

So with probability $1/2$ the final cell has label 2 or 3.

The six possibilities are as follows:

(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

So with probability $2/3$ the final cell has label 1, and with probability $1/6$ the final cell has label 3 or 4.

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

Output Format

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Submit