P9103 - 黑洞合并

内存限制：512 MB 时间限制：3 S

题面：传统评测方式：文本比较上传者：

提交：11 通过：1

宇宙中初始有

n

个黑洞，从左到右编号为

1

到

n

，初始质量依次为

w_{1}, w_{2}, \dots, w_{n}

。
黑洞间即将发生

n - 1

次合并，每次将两个黑洞合并为一个。合并遵循的规律如下：

第 $i$ 次合并开始前，剩余的黑洞数量为 $n - i + 1$ ，从左到右重新编号为 $1, 2, \dots, n - i + 1$ ；
第 $i$ 次合并时，随机选取两个编号为 $x_{i}$ 和 $y_{i}$ ，满足 $x_{i} + y_{i} = n - i + 2$ 的黑洞进行合并，合并后的黑洞随机占据原先黑洞 $x_{i}$ 或 $y_{i}$ 的位置，其质量为 $w_{x_{i}} + w_{y_{i}}$ ；
第 $i$ 次合并会释放出 $w_{x_{i}} \cdot w_{y_{i}} \cdot (w_{x_{i}} + w_{y_{i}})$ 的能量。

n - 1

次合并后，只剩下一个黑洞，请你计算

n - 1

次合并中释放能量之和的期望。答案可能很大，请输出答案对 998244353 取模后的结果。

Input

输入包含多组测试数据：
输入的第一行包含一个整数

T

(

1 \leq T \leq 10

)，表示测试数据的组数。
对于每组测试数据：
第一行包含一个整数

n

(

1 \leq n \leq 1 0^{6}

)，表示初始黑洞的数量。
第二行包含

n

个整数

w_{1}, w_{2}, \dots, w_{n}

(

1 \leq w_{i} \leq 1 0^{6}

)，表示黑洞的初始质量。

Output

对于每组测试数据：
一行包含一个整数，表示答案对 998244353 取模后的结果。

1
3
1 1 1

杭电第9场

9103: 黑洞合并