配点 : $600$ 点

問題文

$1$ から $N$ の番号がついた $N$ 個の箱があります。最初、箱 $i$ には $A_i$ 個のボールが入っています。

あなたは次の操作を $K$ 回繰り返します。

• $N$ 個の箱の中から等確率で $1$ 個選ぶ(この選択は操作ごとに独立である)。選んだ箱にボールを $1$ 個追加する。

$K$ 回の操作が終了した後で箱 $i$ に入っているボールの個数を $B_i$ とするとき、スコアはボールの個数の総積 $\prod_{i=1}^{N}B_i$ になります。

スコアの期待値を $\bmod 998244353$ で求めてください。

注意

求める期待値が既約分数 $p/q$ で表されるとき、$rq\equiv p \pmod{998244353}$ かつ $0\leq r < 998244353$ を満たす整数 $r$ がこの問題の制約のもとで一意に定まります。この $r$ が求める値です。

制約

• $1 \leq N \leq 1000$
• $1 \leq K \leq 10^9$
• $0 \leq A_i \leq 10^9$

入力

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

$N$ $K$

$A_1$ $\ldots$ $A_N$

出力

答えを出力せよ。

3 1
1 2 3

665496245

操作の結果、スコアは次のようになります。

• 操作で箱 $1$ を選んだとき、$2\times 2\times 3=12$
• 操作で箱 $2$ を選んだとき、$1\times 3\times 3=9$
• 操作で箱 $3$ を選んだとき、$1\times 2\times 4=8$

したがって、求める期待値は $\frac{1}{3}(12+9+8)=\frac{29}{3}$ となります。これを $\bmod 998244353$ で表すと $665496245$ になります。

2 2
1 2

499122182

操作の結果、スコアは次のようになります。

• $1$ 回目の操作で箱 $1$ を選び、$2$ 回目の操作で箱 $1$ を選んだとき、$3\times 2=6$
• $1$ 回目の操作で箱 $1$ を選び、$2$ 回目の操作で箱 $2$ を選んだとき、$2\times 3=6$
• $1$ 回目の操作で箱 $2$ を選び、$2$ 回目の操作で箱 $1$ を選んだとき、$2\times 3=6$
• $1$ 回目の操作で箱 $2$ を選び、$2$ 回目の操作で箱 $2$ を選んだとき、$1\times 4=4$

したがって、求める期待値は $\frac{1}{4}(6+6+6+4)=\frac{11}{2}$ となります。

10 1000000000
998244350 998244351 998244352 998244353 998244354 998244355 998244356 998244357 998244358 998244359

138512322