Pic1. 北京東路
Pic2. 北京東路
Pic3. 南京東路
テロリストが $n$ 個の都市の北京東路に爆弾を設置した。初期状態において、第 $i$ の都市にある爆弾の威力は $a_i$ である。
テロリストは $k$ 回の爆発を行うことにした。都市 $i$ で爆発が起こると、その危険度はその都市の爆弾の威力 $a_i$ となる。爆発のたびに、テロリストはエネルギーを操作して爆弾の総威力を一定に保つため、任意の $j \neq i$ に対して $a_j$ は $\frac{a_i}{n-1}$ 増加し、$a_i$ は $0$ になる。
しかし、テロリストの遠隔爆破システムは故障しており、毎回ランダムに一つの都市を選んで爆発させる。
防御のために、小 S は $k$ 回の爆発後の各都市 $i$ における爆弾の威力 $a_i$ の期待値を求めたいと考えている。結果を $998244353$ で割った余りを求めよ。
入力形式
1 行目に 2 つの正整数 $n, k$ が与えられる。
2 行目に $n$ 個の正整数 $a_i$ が与えられる。
出力形式
1 行に、$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 \leq 10^6$、$1 \leq k \leq 10^9$、$0 \leq a_i < 998244353$。