triplea 有一个盒子，里面有 $n(n \ge 1)$ 个球，每个球上都写有一个整数。当盒子里至少有两个球时，triplea 会重复执行以下操作：

• 从盒子里随机、独立且均匀地取出两个球。
• 假设这两个球上的数字分别为 $a$ 和 $b$，triplea 会向盒子里放入一个新球，上面写着数字 $S + P$，其中 $S = a + b$ 是 $a$ 和 $b$ 的和，$P = ab$ 是 $a$ 和 $b$ 的积。

当盒子里只剩下一个球时，操作结束。triplea 想知道，最后一个球上数字的期望值是多少？他立刻得到了答案，并将其留作读者的练习，也就是你。

输入格式

第一行输入包含一个整数 $T(1 \le T \le 20)$，表示测试用例的数量。 对于每个测试用例，第一行输入包含一个整数 $n(1 \le n \le 500)$，表示盒子里初始球的数量。 下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n(0 \le a_i < 998244353)$，表示初始时每个球上写的数字。

输出格式

对于每个测试用例，输出一行一个整数，表示最后一个球上数字的期望值。根据本题的输入约束，可以证明答案可以写成 $\frac{P}{Q}$ 的形式，其中 $P$ 和 $Q$ 是互质的整数且 $Q \not\equiv 0 \pmod{998244353}$。你需要输出 $P \cdot Q^{-1} \pmod{998244353}$ 作为答案，其中 $Q^{-1}$ 是 $Q$ 关于 $998244353$ 的模逆元。

样例

输入 1

2
2
2 2
10
1 2 4 8 16 32 64 128 256 512

输出 1

8
579063023

说明

对于样例中的第一个测试用例，注意 triplea 只能从盒子里取出数字为 2 和 2 的两个球，然后向盒子里放入一个数字为 $(2 + 2) + (2 \times 2) = 8$ 的球。这就是答案。