当前没有测试数据。

G - 球在盒子中

得分：$600$ 分

问题描述

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

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

• 从 $N$ 个盒子中均匀地（每次独立随机地）选择一个盒子。在所选的盒子中增加一个球。

令 $B_i$ 为执行 $K$ 次操作后，第 $i$ 个盒子中的球的个数，并且得分为球的个数的乘积，即 $\prod_{i=1}^{N}B_i$。

求得分的期望值对 $998244353$ 取模的结果。

注意

当所求的期望值表示为一个既约分数 $p/q$ 时，根据该问题的约束，存在唯一的整数 $r$，使得 $rq\equiv p \pmod{998244353}$ 且 $0\leq r < 998244353$。我们要求的答案是 $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}$。这个值对 $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