你拥有 $N$ 只奥术巨兽，每只的攻击力为 $A_i$。

你可以选择巨兽序列的任意非空子序列，并将它们逐一售出。每当你售出一只巨兽时，该子序列中所有剩余未售出的巨兽的攻击力都会增加刚刚售出的那只巨兽的攻击力。

一个子序列的价值定义为：如果以最优的顺序售出该子序列中的其他巨兽，最后剩下的一只巨兽所能达到的最大攻击力。

你的任务是计算该序列所有非空子序列的价值之和。请将结果模 998244353 后输出。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2 \times 10^5$) —— 测试用例的数量。

对于每个测试用例：

第一行包含一个整数 $N$ ($1 \le N \le 2 \times 10^5$) —— 巨兽的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ($0 \le A_i < 998244353$) —— 巨兽的初始攻击力。

保证所有测试用例的 $\sum N \le 2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 所有非空子序列价值之和模 998244353 的结果。

样例

输入样例 1

3
3
1 2 3
6
1 1 4 5 1 4
3
998244350 998244351 998244352

输出样例 1

27
1266
998244328

说明

考虑 $[1, 2, 3]$ 的子序列：

• $[1] \to$ 仅剩下一只巨兽，价值 = 1。
• $[2] \to$ 价值 = 2。
• $[3] \to$ 价值 = 3。
• $[1, 2]$：先售出较大的巨兽 2，留下 1 $\to$ 最终攻击力 = $1 + 2 = 3$。
• $[1, 3]$：先售出 3，留下 1 $\to$ 最终攻击力 = $1 + 3 = 4$。
• $[2, 3]$：先售出 3，留下 2 $\to$ 最终攻击力 = $2 + 3 = 5$。

• $[1, 2, 3]$：

  • 步骤 1：售出 3 $\to$ 剩余序列为 $[1 + 3, 2 + 3] = [4, 5]$。
  • 步骤 2：售出 2（此时攻击力为 5） $\to$ 将其攻击力加到剩余的 4 上，最终攻击力 = $4 + 5 = 9$。
  • 因此，该子序列的价值为 9。

最后，将所有价值相加：$1 + 2 + 3 + 3 + 4 + 5 + 9 = 27$。