Pic1. Calle Beijing Este
Pic2. Calle Beijing Este
Pic3. Calle Nanjing Este
Los terroristas han instalado bombas en $n$ ciudades a lo largo de la Calle Beijing Este. Inicialmente, la potencia de la bomba en la ciudad $i$ es $a_i$.
Los terroristas deciden realizar $k$ explosiones. En una explosión en la ciudad $i$, el nivel de peligro es igual a la potencia de la bomba en esa ciudad, $a_i$. Después de cada explosión, debido a que los terroristas pueden manipular la energía para mantener constante la potencia total de las bombas, para cualquier $j \neq i$, $a_j$ aumenta en $\frac{a_i}{n-1}$, mientras que $a_i$ se reduce a cero.
Sin embargo, el sistema de detonación remota de los terroristas está averiado y selecciona aleatoriamente una ciudad para explotar en cada ocasión.
Para facilitar la defensa, Xiao S quiere saber cuál es el valor esperado de la potencia de la bomba $a_i$ en la ciudad $i$ después de realizar $k$ explosiones, calculado módulo $998244353$.
Entrada
La primera línea contiene dos enteros positivos $n, k$.
La segunda línea contiene $n$ enteros positivos $a_i$.
Salida
Una línea con $n$ enteros positivos, que representan los valores esperados.
Ejemplos
Entrada 1
6 3 2 1 0 0 3 5
Salida 1
381994841 86514512 789278536 789278536 677475170 270191475
Entrada 2
2 1 1 2
Salida 2
499122178 499122178
Restricciones
| Subtarea | Puntuación | Restricciones adicionales |
|---|---|---|
| 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 | Ninguna |
Para todos los casos: $2 \leq n \leq 10^6$, $1 \leq k \leq 10^9$, $0 \leq a_i < 998244353$.