#2320. 「清华集训 2017」生成树计数

内存限制:1024 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

在一个 ss 个点的图中,存在 sns-n 条边,使图中形成了 nn 个连通块,第 ii 个连通块中有 aia_i 个点。

现在我们需要再连接 n1n-1 条边,使该图变成一棵树。对一种连边方案,设原图中第 ii 个连通块连出了 did_i 条边,那么这棵树 TT 的价值为:

val(T)=(i=1ndim)(i=1ndim) \mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right)

你的任务是求出所有可能的生成树的价值之和,对 998244353998244353 取模。

输入格式

输入的第一行包含两个整数 n,mn,m,意义见题目描述。

接下来一行有 nn 个整数,第 ii 个整数表示 aia_i (1ai<998244353)(1\le a_i< 998244353)

  • 你可以由 aia_i 计算出图的总点数 ss,所以在输入中不再给出 ss 的值。

输出格式

输出包含一行一个整数,表示答案。

样例

样例输入 1

3 1
2 3 4

样例输出 1

1728

样例解释 1

ii 表示大小为 ii 的原连通块,我们在连通块之间的连边有以下三种可能:

  • 2342-3-4
  • 3243-2-4
  • 2432-4-3

价值和为:

(2×32×4×2+3×22×4×2+2×42×3×2)×(1+2+1)=1728(2×3^2 ×4×2+3×2^2 ×4×2+2×4^2 ×3×2)×(1+2+1)=1728

样例 2

见附加文件

数据范围与提示

本题共有 2020 个测试点,每个测试点 55 分。

  • 20%20\% 的数据中,n500n\le500

  • 另外 20%20\% 的数据中,n3000n \le 3000

  • 另外 10%10\% 的数据中,n10010,m=1n \le 10010, m = 1

  • 另外 10%10\%的数据中,n10015,m=2n \le 10015,m = 2

  • 另外 20%20\% 的数据中,所有 aia_i 相等。

  • 100%100\% 的数据中,n3×104,m30n \le 3\times 10^4,m \le 30

其中,每一个部分分的测试点均有一定梯度。