DreamGrid 正在驾驶一艘宇宙飞船从火星前往地球。

轨道上有 $n$ 个加速器可以为飞船加速。第 $i$ 个加速器的加速因子为 $a_i$。飞船将依次通过这些加速器。初始时，飞船的速度为 $0$。当飞船通过一个加速器时，它会从加速器获得能量，速度随之改变。形式化地，如果加速因子为 $A$，加速前的速度为 $v$，则加速后的速度变为 $v' = (v + 1) \times A$。

然而，这 $n$ 个加速器的顺序是随机打乱的。DreamGrid 现在不知道飞船通过加速器的顺序。你能告诉他通过所有 $n$ 个加速器后的期望速度是多少吗？

可以证明期望速度是一个有理数。假设答案可以表示为 $\frac{u}{d}$，其中 $\gcd(u, d) = 1$，你需要输出一个整数 $r$，满足 $rd \equiv u \pmod{998\,244\,353}$ 且 $0 \le r < 998\,244\,353$。可以证明这样的 $r$ 存在且唯一。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 100\,000$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示加速器的数量。 下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示加速因子。

保证所有测试数据的 $n$ 之和不超过 $100\,000$。

输出格式

对于每组测试数据，输出一行包含整数 $r$。

样例

输入 1

3
3
1 2 3
1
10
4
5 5 5 5

输出 1

665496247
10
780

说明

对于第一个样例，加速器有 6 种排列方式：

$1,2,3 : v = ((((0 + 1) \times 1 + 1) \times 2) + 1) \times 3 = 15$ $1,3,2 : v = ((((0 + 1) \times 1 + 1) \times 3) + 1) \times 2 = 14$ $2,1,3 : v = ((((0 + 1) \times 2 + 1) \times 1) + 1) \times 3 = 12$ $2,3,1 : v = ((((0 + 1) \times 2 + 1) \times 3) + 1) \times 1 = 10$ $3,1,2 : v = ((((0 + 1) \times 3 + 1) \times 1) + 1) \times 2 = 10$ $3,2,1 : v = ((((0 + 1) \times 3 + 1) \times 2) + 1) \times 1 = 9$

因此期望速度为 $\frac{15+14+12+10+10+9}{3!} = \frac{70}{6}$。