题目背景

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$ 个正整数，表示期望值。

6 3
2 1 0 0 3 5

381994841 86514512 789278536 789278536 677475170 270191475 

2 1
1 2

499122178 499122178 

提示

数据范围

子任务编号	分值	额外限制
1	20	$n,k\leq 5$
2		$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$。