問題文

整数 $N$ が与えられます．

すぬけくんはこれから，以下の操作を行います．

• 変数 $x$ を用意し，ランダムに選んだ $0$ 以上 $N$ 以下の整数で初期化する．各 $0 \\leq i \\leq N$ に対し，$x=i$ と初期化する確率は $A_i/10^9$ である．
• 次の操作を $K$ 回繰り返す．
  • 確率 $x/N$ で $x$ の値を $1$ 減らし，確率 $1-x/N$ で $x$ の値を $1$ 増やす． （ここで，操作後も $x$ の値が必ず $0$ 以上 $N$ 以下であることに注意）

各 $i=0,1,\\cdots,N$ について，すべての操作が終了したあとに $x=i$ である確率を $\\pmod{998244353}$ で求めてください．

確率 $\\pmod{998244353}$ の定義

求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $\\frac{P}{Q}$ で表した時、$Q \\neq 0 \\pmod{998244353}$ となることも証明できます。 よって、$R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$ を満たす整数 $R$ が一意に定まります。 この $R$ を答えてください。

制約

• $1 \\leq N \\leq 100000$
• $0 \\leq A_i$
• $\\sum_{0 \\leq i \\leq N}A_i = 10^9$
• $1 \\leq K \\leq 10^9$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

$N$ $K$ $A_0$ $A_1$ $\\cdots$ $A_N$

出力

各 $i=0,1,\\cdots,N$ について，すべての操作が終了したあとに $x=i$ である確率を $\\pmod{998244353}$ で出力せよ．

入力例 1

2 1
0 1000000000 0

出力例 1

499122177 0 499122177

最初は必ず $x=1$ と初期化します． その後の操作では．確率 $1/2$ で $x$ の値を $1$ 減らし，確率 $1/2$ で $x$ の値を $1$ 増やします． 最終的に $x=0,1,2$ となる確率は，それぞれ $1/2,0,1/2$ です．

入力例 2

4 2
200000000 200000000 200000000 200000000 200000000

出力例 2

723727156 598946612 349385524 598946612 723727156

入力例 3

10 100
21265166 263511538 35931763 26849698 108140810 134702248 36774526 147099145 58335759 4118743 163270604

出力例 3

505314898 24510700 872096939 107940764 808162829 831195162 314651262 535843032 665830283 627881537 696038713