E. Школьные клубы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В школе Гомера есть $$$n$$$ студентов, которые любят клубы.

Изначально есть $$$m$$$ клубов, и каждый из $$$n$$$ студентов находится ровно в одном клубе. Другими словами, в $$$i$$$-м клубе $$$a_i$$$ студентов для $$$1 \leq i \leq m$$$, причем $$$a_1+a_2+\dots+a_m = n$$$.

$$$n$$$ студентов настолько недружелюбны, что каждый день один (выбранный равновероятно среди всех $$$n$$$ студентов) из них злится. Разозлившийся студент сделает одну из следующих вещей.

  • С вероятностью $$$\frac 1 2$$$ он покидает свой нынешний клуб, затем сам создает новый клуб и присоединяется к нему. В новом клубе, который он создает, есть только один ученик (он сам).
  • С вероятностью $$$\frac 1 2$$$ он не создает новый клуб. В этом случае он меняет свой клуб на некоторый (возможно, на тот же клуб, в котором он находится в настоящее время) с вероятностью, пропорциональной количеству студентов в нем. Формально, пусть есть $$$k$$$ клубов, и в $$$i$$$-м клубе есть $$$b_i$$$ студентов для $$$1 \leq i \leq k$$$ (до того, как студент разозлится). Он покидает свой текущий клуб, а затем присоединяется к $$$i$$$-му клубу с вероятностью $$$\frac {b_i} {n}$$$.

Отметим, что когда клуб становится пустым, студенты никогда не присоединятся к нему, потому что любой ученик, который разозлится, присоединится к пустому клубу с вероятностью $$$0$$$ в соответствии с приведенным выше утверждением.

Гомер интересуется ожидаемым количеством дней до того момента, когда все студенты окажутся в одном и том же клубе впервые.

Мы можем доказать, что ответ может быть представлен в виде рационального числа $$$\frac p q$$$ с $$$\gcd(p, q) = 1$$$. Вы должны найти значение $$$pq^{-1} \bmod 998\,244\,353$$$. Можно показать, что $$$q \bmod 998\,244\,353 \neq 0$$$ при заданных ограничениях задачи.

Входные данные

Первая строка содержит одно целое положительное число $$$m$$$ ($$$1 \leq m \leq 1000$$$) — начальное количество клубов.

Вторая строка содержит $$$m$$$ положительных целых чисел $$$a_1, a_2, \dots, a_m$$$ ($$$1 \leq a_i \leq 4 \cdot 10^8$$$) с $$$1 \leq a_1+a_2+\dots+a_m \leq 4 \cdot 10^8$$$, где $$$a_i$$$ обозначает количество учеников в $$$i$$$-м клубе изначально.

Выходные данные

Выведите одно целое число — ожидаемое количество дней, пока все студенты не окажутся в одном клубе впервые, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
2
1 1
Выходные данные
4
Входные данные
2
1 2
Выходные данные
18
Входные данные
3
1 1 1
Выходные данные
21
Входные данные
1
400000000
Выходные данные
0
Входные данные
10
1 2 3 4 5 6 7 8 9 10
Выходные данные
737609878
Примечание

В первом примере независимо от того, какой студент разозлится, два студента с вероятностью $$$\frac 1 4$$$ попадут в один и тот же клуб. Таким образом, ожидаемое количество дней, пока каждый ученик не окажется в одном клубе, должно составлять $$$4$$$.

Во втором примере мы отмечаем, что в первый день:

  • Единственный студент в первом клубе разозлится с вероятностью $$$\frac 1 3$$$. Если он разозлится, то создаст новый клуб и присоединится к нему с вероятностью $$$\frac 1 2$$$ (в этом случае будет три клуба, в которых будут состоять $$$0, 1, 2$$$ студента, соответственно); покинет свой текущий клуб и присоединится ко второму с вероятностью $$$\frac 1 2 \cdot \frac 2 3 = \frac 1 3$$$, или останется с вероятностью $$$\frac 1 2 \cdot \frac 1 3 = \frac 1 6$$$;
  • Каждый из двух студентов во втором клубе разозлится с вероятностью $$$\frac 1 3$$$. Если один из них разозлится, то создаст новый клуб и присоединится к нему с вероятностью $$$\frac 1 2$$$, покинет свой текущий клуб и присоединится ко второму с вероятностью $$$\frac 1 2 \cdot \frac 1 3 = \frac 1 6$$$, или останется с вероятностью $$$\frac 1 2 \cdot \frac 2 3 = \frac 1 3$$$.

В четвертом примере изначально есть только один клуб. То есть каждый студент уже в одном клубе. Так что ответ — $$$0$$$.