题目描述

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

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

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

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

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

输入格式

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

$N$ $K$ $A_1$ $\ldots$ $A_N$

输出格式

答えを出力せよ。

题目大意

有 $n$ 个盒子，初始时第 $i$ 个盒子内有 $a_i$ 个小球，进行 $k$ 次操作后，每次操作等概率随机选择一个盒子放入一个小球，设 $k$ 次操作后每个盒子的小球个数为 $b_i$，那么得分为 $\prod_{i=1}^n b_i$。求出期望得分。

• $n\leq 1000,k,a_i\leq 10^9$

3 1
1 2 3

665496245

2 2
1 2

499122182

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

138512322

提示

注意

求める期待値が既約分数 $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$

Sample Explanation 1

操作の結果、スコアは次のようになります。 - 操作で箱 $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$ になります。

Sample Explanation 2

操作の結果、スコアは次のようになります。 - $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}$ となります。