黑洞合并

Problem Description

宇宙中初始有 $n$ 个黑洞，从左到右编号为 $1$ 到 $n$，初始质量依次为 $w_1, w_2,\cdots, w_n$。 黑洞间即将发生 $n - 1$ 次合并，每次将两个黑洞合并为一个。合并遵循的规律如下：

• 第 $i$ 次合并开始前，剩余的黑洞数量为 $n - i + 1$，从左到右 重新编号 为 $1, 2, \cdots, 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 10^6$)，表示初始黑洞的数量。 第二行包含 $n$ 个整数 $w_1, w_2, \cdots, w_n$ ($1\leq w_i\leq 10^6$)，表示黑洞的初始质量。

Output

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

Sample Input

1
3
1 1 1

Sample Output

8

Source

2024“钉耙编程”中国大学生算法设计超级联赛（9）