#38. 【清华集训2017】生成树计数

题目类型:传统型 时间限制:5000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

在一个 $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 4

output

1728

explanation

令 $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}$