Rys. 1. Ulica Beijing Donglu
Rys. 2. Ulica Beijing Donglu
Rys. 3. Ulica Nanjing Donglu
Terroryści podłożyli bomby w $n$ miastach przy ulicy Beijing Donglu. Początkowa siła bomby w $i$-tym mieście wynosi $a_i$.
Terroryści zdecydowali się przeprowadzić $k$ eksplozji. W pojedynczej eksplozji w mieście $i$, poziom zagrożenia jest równy sile bomby w tym mieście, czyli $a_i$. Po każdej eksplozji, ponieważ terroryści mogą manipulować energią tak, aby całkowita siła bomb pozostała niezmienna, dla każdego $j \neq i$ wartość $a_j$ wzrasta o $\frac{a_i}{n-1}$, natomiast $a_i$ zostaje wyzerowane.
Jednakże system zdalnego sterowania eksplozjami uległ awarii i za każdym razem losowo wybiera miasto, w którym nastąpi wybuch.
W celu ułatwienia obrony, mały S chce wiedzieć, jaka jest wartość oczekiwana siły bomby $a_i$ w każdym mieście po $k$ eksplozjach, modulo $998244353$.
Wejście
Pierwsza linia zawiera dwie liczby całkowite dodatnie $n, k$.
Druga linia zawiera $n$ liczb całkowitych nieujemnych $a_i$.
Wyjście
Jedna linia zawierająca $n$ liczb całkowitych, reprezentujących wartości oczekiwane.
Przykład 1
Wejście 1
6 3 2 1 0 0 3 5
Wyjście 1
381994841 86514512 789278536 789278536 677475170 270191475
Przykład 2
Wejście 2
2 1 1 2
Wyjście 2
499122178 499122178
Ograniczenia
| Numer podzadania | Punkty | Dodatkowe ograniczenia |
|---|---|---|
| 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 | brak |
Dla wszystkich danych: $2 \leq n \leq 10^6$, $1 \leq k \leq 10^9$, $0 \leq a_i < 998244353$.