Pic1. Beijing East Road
Pic2. Beijing East Road
Pic3. Nanjing East Road
Terrorists have planted bombs in $n$ cities along Beijing East Road, with the initial power of the bomb in city $i$ being $a_i$.
The terrorists decide to carry out $k$ explosions. In an explosion at city $i$, the danger level is the power of the bomb in that city, $a_i$. After each explosion, because the terrorists can manipulate energy to keep the total power of the bombs constant, for any $j \neq i$, $a_j$ increases by $\frac{a_i}{n-1}$, while $a_i$ becomes zero.
However, the terrorists' remote detonation system is malfunctioning, and it chooses a city to explode at random each time.
For defense purposes, Xiao S wants to know the expected value of the bomb power $a_i$ in city $i$ after $k$ explosions, modulo $998244353$.
Input
The first line contains two positive integers $n, k$.
The second line contains $n$ non-negative integers $a_i$.
Output
A single line containing $n$ integers, representing the expected values.
Examples
Input 1
6 3 2 1 0 0 3 5
Output 1
381994841 86514512 789278536 789278536 677475170 270191475
Input 2
2 1 1 2
Output 2
499122178 499122178
Constraints
| Subtask ID | Score | Additional Constraints |
|---|---|---|
| 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 | None |
For all data: $2\leq n\leq10^6$, $1\leq k\leq10^9$, $0\leq a_i<998244353$.