셀 병합

Bessie는 한 줄로 늘어선 셀로 이루어진 온라인 게임을 즐기고 있다. 각 셀에는 레이블과 크기가 있다. 셀은 이웃한 셀을 계속 먹고, 마지막에는 승자 하나만 남는다.

셀은 왼쪽에서 오른쪽으로 $N$개 ($2\le N\le 5000$) 놓여 있으며, 왼쪽부터 $1$에서 $N$까지 레이블이 붙어 있다. 처음 크기는 $s_1, s_2, \dots, s_N$이다 ($1\le s_i\le 10^5$).

셀이 두 개 이상 남아 있는 동안, 인접한 셀 한 쌍을 균등한 확률로 무작위로 골라 하나의 새 셀로 합친다. 레이블 $a$, 현재 크기 $c_a$인 셀이 레이블 $b$, 현재 크기 $c_b$인 셀과 합쳐지면, 새 셀의 크기는 $c_a+c_b$이다. 레이블은 더 큰 셀의 레이블을 따른다. 크기가 같으면 레이블이 더 큰 쪽이 된다. 식으로 쓰면 다음과 같다.

$\text{결과 레이블} = \begin{cases} a & c_a > c_b \\ b & c_a < c_b \\ \max(a,b) & c_a = c_b \end{cases}$

$1$부터 $N$까지의 각 레이블 $i$에 대해, 최종 셀의 레이블이 $i$일 확률을 구하라. 이 확률은 $\frac{a_i}{b_i}$로 나타낼 수 있으며, $b_i\not\equiv 0 \pmod{10^9+7}$이다. $a_i b_i^{-1} \bmod (10^9+7)$를 출력하라.

첫 줄에 $N$이 주어진다.

다음 줄에 $s_1, s_2, \dots, s_N$이 주어진다.

$1$부터 $N$까지의 각 레이블 $i$에 대해, 최종 셀의 레이블이 $i$일 확률을 10^9+7로 나눈 나머지로 한 줄에 하나씩 출력한다.