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 取模后的结果。

1
3
1 1 1

8