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$。