Слайм и его \(n\) друзей на вечеринке. Слайм придумал игру для своих друзей.
В начале игры у \(i\)-го игрока есть \(a_i\) бисквитов. Каждую секунду Слайм выберет один бисквит равновероятно среди \(a_1 + a_2 + \ldots + a_n\) бисквитов, и владелец этого бисквита передает его случайному игроку, равновероятно среди \(n-1\) игроков кроме себя. Игра закончится, когда у одного игрока будут все бисквиты.
Как хозяин вечеринки, Слайм хочет узнать математическое ожидание времени, когда игра закончится, чтобы успеть провести следующее мероприятие.
Так как ответ может быть представлен в виде рациональной дроби \(\frac{p}{q}\) для взаимно простых \(p\) и \(q\), выведите его в форме \((p \cdot q^{-1})\mod 998\,244\,353\). Можно доказать, что \(q\mod 998\,244\,353 \neq 0\).
Выходные данные
Выведите одно число: математическое ожидание времени, когда игра закончится, по модулю \(998\,244\,353\).
Примечание
В первом примере, вероятность, что игрок \(1\) передаст игроку \(2\) бисквит равна \(\frac{1}{2}\), а вероятность что игрок \(2\) передаст игроку \(1\) бисквит равна \(\frac{1}{2}\). В любом случае игра продлится ровно \(1\) секунду, так как все бисквиты будут у одного игрока спустя \(1\) секунду, поэтому ответ равен \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 1
|
1
|
|
2
|
2
1 2
|
3
|
|
3
|
5
0 0 0 0 35
|
0
|
|
4
|
5
8 4 2 0 1
|
801604029
|