在一个 $s$ 个点的图中，存在 $s-n$ 条边，使图中形成了 $n$ 个连通块，第 $i$ 个连通块中有 $a_i$ 个点。
现在我们需要再连接 $n-1$ 条边，使该图变成一棵树。对一种连边方案，设原图中第 $i$ 个连通块连出了 $d_i$ 条边，那么这棵树 $T$ 的价值为：
$$ \mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right) $$
你的任务是求出所有可能的生成树的价值之和，对 $998244353$ 取模。
输入格式
输入的第一行包含两个整数 $n,m$，意义见题目描述。
接下来一行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$ $(1\le a_i< 998244353)$。
- 你可以由 $a_i$ 计算出图的总点数 $s$，所以在输入中不再给出 $s$ 的值。
输出格式
输出包含一行一个整数，表示答案。
样例一
input
3 1
2 3 4output
1728explanation
令 $i$ 表示大小为 $i$ 的原连通块，我们在连通块之间的连边有以下三种可能：
2 - 3 - 4
3 - 2 - 4
2 - 4 - 3价值和为：$ \left(2\times 3^2\times 4\times 2+3\times 2^2\times 4 \times 2+2\times 4^2\times 3\times 2\right)\times (1+2+1)=1728 $
样例二
见样例数据下载
限制与约定
本题共有 20 个测试点，每个测试点 5 分。
- 20% 的数据中，$n\le 500$ 。
- 另外 20% 的数据中，$n\le 3000$ 。
- 另外 10% 的数据中，$n\le 10000$, $m=1$ 。
- 另外 10% 的数据中，$n\le 10000, m=2$ 。
- 另外 20% 的数据中，所有 $a_i$ 相等 。
- 100% 的数据中，$n\le 3\times 10^4, m\le 30$ 。
其中，每一个部分分的测试点均有一定梯度。
时间限制：$5\texttt{s}$
空间限制：$512\texttt{MB}$
