問題文

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

出力

答えを出力せよ。

入力例 1

3 1
1 2 3

出力例 1

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 2
1 2

出力例 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}$ となります。

入力例 3

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

出力例 3

138512322