Pic1. 北京東路
Pic2. 北京東路
Pic3. 南京東路
恐怖分子在 $n$ 個城市的北京東路上安裝了炸彈，初始第 $i$ 個城市中的炸彈威力為 $a_i$。
恐怖分子決定進行 $k$ 次爆炸。一次 $i$ 城市的爆炸中，其危險度為這個城市中炸彈的威力 $a_i$。每次爆炸之後，由於恐怖分子可以操控能量以保持炸彈總威力不變，對於任意 $j\neq i$，$a_j$ 將增加 $\frac{a_i}{n-1}$，而 $a_i$ 將清零。
然而，恐怖分子的遙控爆炸系統壞了，每次都會隨機選擇一個城市進行爆炸。
為了方便防禦，小 S 想知道進行 $k$ 次爆炸後，$i$ 城市中炸彈的威力 $a_i$ 的期望值是多少，對 $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$。