题目描述
在一个 s 个点的图中,存在 s−n 条边,使图中形成了 n 个连通块,第 i 个连通块中有 ai 个点。
现在我们需要再连接 n−1 条边,使该图变成一棵树。对一种连边方案,设原图中第 i 个连通块连出了 di 条边,那么这棵树 T 的价值为:
val(T)=(i=1∏ndim)(i=1∑ndim)你的任务是求出所有可能的生成树的价值之和,对 998244353 取模。
输入格式
输入的第一行包含两个整数 n,m,意义见题目描述。
接下来一行有 n 个整数,第 i 个整数表示 ai (1≤ai<998244353)。
- 你可以由 ai 计算出图的总点数 s,所以在输入中不再给出 s 的值。
输出格式
输出包含一行一个整数,表示答案。
提示
令 i 表示大小为 i 的原连通块,我们在连通块之间的连边有以下三种可能:
- 2−3−4
- 3−2−4
- 2−4−3
价值和为:
(2×32×4×2+3×22×4×2+2×42×3×2)×(1+2+1)=1728
本题共有 20 个测试点,每个测试点 5 分。
-
20% 的数据中,n≤500。
-
另外 20% 的数据中,n≤3000。
-
另外 10% 的数据中,n≤10010,m=1。
-
另外 10%的数据中,n≤10015,m=2。
-
另外 20% 的数据中,所有 ai 相等。
-
100% 的数据中,n≤3×104,m≤30。
其中,每一个部分分的测试点均有一定梯度。