宇宙中初始有 $n$ 个黑洞，从左到右编号为 $1$ 到 $n$，初始质量依次为 $w_1, w_2, \cdots, w_n$。

黑洞间即将发生 $n−1$ 次合并，每次将两个黑洞合并为一个。合并遵循的规律如下：

• 第 $i$ 次合并开始前，剩余的黑洞数量为 $n−i+1$，从左到右 重新编号 为 $1,2,⋯,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}(w_{x_i}+w_{y_i})$ 的能量。

$n−1$ 次合并后，只剩下一个黑洞，请你计算 $n−1$ 次合并中释放能量之和的期望。答案可能很大，请输出答案对 $998244353$ 取模后的结果。

输入包含多组测试数据：

输入的第一行包含一个整数 $T (1≤T≤10)$，表示测试数据的组数。

对于每组测试数据：

第一行包含一个整数 $n (1≤n≤10^6 )$，表示初始黑洞的数量。

第二行包含 $n$ 个整数 $w_1, w_2, \cdots, w_n(1 \le w_i \le 10^6)$，表示黑洞的初始质量。

对于每组测试数据：

一行包含一个整数，表示答案对 $998244353$ 取模后的结果。