「KDOI-07」能量场

4202 年，小 K 作为一名已经工作了 3143 天的 gaLaxy enGineer Master，在 XS41 星系的 OIPA115 星球上建立了据点，帮助人类探索未知。在这里，他建起了一些能量场。原本他决定使用一些卒来运输能量，然而在他操控的两个红色卒碰撞并损失所有能量后决定还是应该使用能量管道连接他们，~~并使能量管道呈 $(180+\mathrm{eps})^\circ$ 角~~。

小 K 有 $n$ 个能量场，第 $i$ 个能量场存储 $a_i$ 点能量。 小 K 在能量场之间建立了 $n$ 条不同的双向能量管道，使得能量场两两连通。 对于一条能量管道，它的能量级为两端能量场能量之和。 小 K 对一组 $n$ 个不同能量管道集合的满意度是所有能量管道能量级的乘积。 现在小 K 想知道，对于所有不同的合法的搭建能量管道的方式，满意度的总和是多少。由于小 K 的满意度是一个 $[0,998244353)$ 之间的整数，所以你只需要输出满意度总和对 $998244353$ 取模后的值即可。 两种搭建管道的方式是不同的当且仅当存在至少一条管道连接能量场 $i,j$，且恰好在其中一种搭建管道的方式中出现。 --- **【形式化题意】** 有一个 $n$ 个点的完全图 $G(V,E)$。每个点有点权 $a_i$。$i,j$ 两点之间的边权 $w_{i,j}=a_i+a_j$。 定义一个连通子图 $G'(V,E')$ 使得 $E'\in E$ 的权值为 $\prod_{e\in E'}w_e$。注意，子图的点集是全集。 求 $G(V,E)$ 的连通子图中所有基环树的权值和，对 $998244353$ 取模。 基环树要求无重边无自环。

第一行一个正整数 $n$，表示能量场数量。 第二行 $n$ 个非负整数 $a_i$，表示第 $i$ 个能量场存储的能量。

一行，一个非负整数，表示对于所有不同搭建能量管道的方式，满意度的总和，对 $998244353$ 取模。

3
1 2 3

60

4
1 2 3 4

8629

7
1 9 1 9 8 1 0

311816897

16
2 0 0 9 0 2 2 8 2 0 0 9 0 8 1 5

871736512

### 样例解释 1 可能的基环树形态只有包含三个点的环，环边 $(1,2),(1,3),(2,3)$ 的边权分别是 $3,4,5$，乘积为 $60$。 ### 数据规模与约定 **本题采用捆绑测试。** | $\mathrm{Subtask}$ | $n\leq$ | 特殊性质 | 分数 | |:--:|:--:|:--:|:--:| | $1$ | $3$ | | $1$ | | $2$ | $7$ | | $4$ | | $3$ | $24$ | $\checkmark$ | $5$ | | $4$ | $12$ | | $10$ | | $5$ | $18$ | | $10$ | | $6$ | $20$ | | $5$ | | $7$ | $23$ | | $5$ | | $8$ | $24$ | | $30$ | | $9$ | $50$ | | $15$ | | $10$ | $200$ | | $5$ | | $11$ | $500$ | | $5$ | | $12$ | $1000$ | | $5$ | 特殊性质：保证 $\forall i\in[1,n],a_i=499122177$。 对于所有数据，保证 $3\leq n\leq 1000$，$0\leq a_i<998244353$。