题目描述

我们有 $N$ 个编号为 $1$ 到 $N$ 的盒子。初始时，盒子 $i$ 中包含 $A_i$ 个球。

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

• 均匀随机地选择一个盒子（每次独立选择）。向选中的盒子中添加一个球。

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

输出

输出答案。

示例输入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}$。该值对 $998244353$ 取模为 $665496245$。

示例输入2

2 2
1 2

示例输出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}$。

示例输入3

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

示例输出3

138512322