Рис. 1. Пекинская восточная улица
Рис. 2. Пекинская восточная улица
Рис. 3. Нанкинская восточная улица
Террористы установили бомбы на Пекинской восточной улице в $n$ городах. Изначально мощность бомбы в $i$-м городе равна $a_i$.
Террористы решили произвести $k$ взрывов. При взрыве в городе $i$ его опасность равна текущей мощности бомбы $a_i$. После каждого взрыва, поскольку террористы могут управлять энергией так, чтобы суммарная мощность бомб оставалась неизменной, для любого $j \neq i$ значение $a_j$ увеличивается на $\frac{a_i}{n-1}$, а значение $a_i$ становится равным $0$.
Однако система дистанционного подрыва террористов неисправна, и каждый раз она выбирает город для взрыва случайным образом.
Для организации защиты Сяо С. хочет узнать математическое ожидание мощности бомбы $a_i$ в каждом городе $i$ после $k$ взрывов. Ответ необходимо вывести по модулю $998244353$.
Входные данные
Первая строка содержит два целых положительных числа $n$ и $k$.
Вторая строка содержит $n$ целых неотрицательных чисел $a_i$.
Выходные данные
Одна строка, содержащая $n$ целых чисел, представляющих математические ожидания мощностей.
Примеры
Входные данные 1
6 3 2 1 0 0 3 5
Выходные данные 1
381994841 86514512 789278536 789278536 677475170 270191475
Входные данные 2
2 1 1 2
Выходные данные 2
499122178 499122178
Ограничения
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 20 | $n,k\leq 5$ |
| 2 | 20 | $n,k\leq 10^3$ |
| 3 | 25 | $k\leq 10^6$ |
| 4 | 15 | $a_1=1,a_2=a_3=\dots=a_n=0$ |
| 5 | 20 | Нет |
Для всех данных: $2\leq n\leq10^6$, $1\leq k\leq10^9$, $0\leq a_i<998244353$.