盒子里的球

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的盒子。初始时,盒子 $i$ 中有 $A_i$ 个球。

你将重复以下操作 $K$ 次。

从 $N$ 个盒子中均匀随机选择一个盒子(每次独立)。向选中的盒子中添加一个球。

设 $K$ 次操作后盒子 $i$ 中的球数为 $B_i$,得分为球数的乘积 $\prod_{i=1}^{N} B_i$。

求得分期望值模 $998244353$ 的值。

输入格式

输入按以下格式从标准输入给出。

$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}$。该值模 $998244353$ 为 $665496245$。

2 2
1 2

499122182

操作结束后,得分如下。

第一次选择盒子 $1$,第二次选择盒子 $1$ 时,$3 \times 2 = 6$。

第一次选择盒子 $1$,第二次选择盒子 $2$ 时,$2 \times 3 = 6$。

第一次选择盒子 $2$,第二次选择盒子 $1$ 时,$2 \times 3 = 6$。

第一次选择盒子 $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

数据范围

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

提示

当所求期望值表示为不可约分数 $p/q$ 时,在本问题的约束下,存在唯一的整数 $r$,满足 $rq \equiv p \pmod{998244353}$ 且 $0 \le r \lt 998244353$。这个 $r$ 就是我们所求的值。