Замечание: ограничение по памяти для этой задачи 512 Мбт, в два раза больше,
чем по умолчанию **
Беси играет в известную он-лайн-игру, в которой имеется множество
ячеек разных меток и размеров. Ячейки поедают другие до тех пор, пока
не останется одна - победитель.
Имеется \(N\) (\(2\le N\le 5000\)) ячеек в строке, помеченных \(1\dots 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\)
и метку, равную метке большей ячейки и большей метке в случае равенства
ячеек.
Формально метка вычисляется так
$\begin{cases}
a & ca > cb \\
b & ca < cb \\
\max(a,b) & ca = cb
\end{cases}.$
Для каждой метки \(i\) в интервале \(1\dots N\) вероятность того, что
финальная ячейка имеет метку \(i\) может быть выражена в виде
\(\frac{a_i}{b_i}\) где
\(b_i\not\equiv 0\pmod{10^9+7}\).
выведите \(a_ib_i^{-1}\pmod{10^9+7}\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит число
\(N\).
Следующая строка содержит \(s_1,s_2,\dots, s_N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Вероятности того что финальная ячейка имеет метку \(i\) (по модулю \(10^9+7\))
для каждого \(i\) в интервале \(1\dots N\) - на отдельной строке
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1 1
|
0
500000004
500000004
|