F-到底是多少分啊_第20届上海大学程序设计联赛春季赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

在旅途的终点，你终于看到了大魔王小 X。

小 X 准备玩一个游戏，这个游戏规则如下：

对于一个含有 n 个数的数组 a。小 X 必须执行如下操作 t 次：

选择数组中的某一个数，给它加上 1。

经过这样 t 次操作后得到的数组 b。小 X 的得分是数组 b 中所有数的乘积。

显然，在不同的操作过程后，最终可能获得不同的数组 b。我们称两个数组是不同的，当且仅当这两个数组中至少有一个数不同，即两个数组 p, q 不同当且仅当存在 i 使得 pi≠qi 。

如果小 X 在所有不同的数组 b 中随机取一个作为最终结果，那么他的期望得分是多少？

输入描述:

第一行包含两个整数 $n$ , $t$ ( $1\leq n\leq 3000$ , $1\leq t\leq 3000$ )，分别表示数组中元素的个数和操作的总次数。

第二行包含 n 个整数 $a_{1},a_{2},\ldots, a_{n}$ $(0\leq a_{i}\leq10^9)$ ，分别表示数组 a 的每个元素。

输出描述:

在一行输出一个整数表示得分的期望值对 998244353 取模的结果。

期望是分数 $\frac{p}{q}$ ，取模后的结果应当为 $p \times q^{-1} \,(\bmod 998244353)$ 。形式化地说，你需要输出一个整数 $r$ 满足 $0\leq r < 998244353$ 且 $r\times q\equiv p \,(\bmod 998244353)$ 。

由于费马小定理，我们易推得 $q^{-1} ≡ q^{998244351} (\bmod 998244353)$

示例1

输入

复制

3 2
1 2 3

输出

复制

332748132