D. Arcane Behemoths
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$N$$$ Arcane Behemoths, each with an attack value $$$A_i$$$.

You may choose any non-empty subsequence of Behemoths and sell them one by one. Whenever you sell a Behemoth, each remaining unsold Behemoth in the subsequence increases its attack value by the attack value of the Behemoth you just sold.

The value of a subsequence is the maximum attack value the last remaining Behemoth can achieve, if the other Behemoths in the subsequence are sold in an optimal order.

Your task is to compute the sum of values over all non-empty subsequences of the sequence. Print the result modulo $$$998244353$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 2 \times 10^5$$$) — the number of test cases.

For each test case, the first line contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \times 10^5$$$) — the number of Behemoths.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ $$$(0 \leq A_i \lt 998244353)$$$ — the initial attack values of the Behemoths.

It is guaranteed that $$$\sum N \leq 2\times 10^5$$$ over all test cases.

Output

For each test case, print a single integer — the sum of values over all non-empty subsequences modulo $$$998244353$$$.

Example
Input
3
3
1 2 3
6
1 1 4 5 1 4
3
998244350 998244351 998244352
Output
27
1266
998244328
Note

Consider the subsequences of $$$[1,2,3]$$$:

  • $$$[1]$$$ → only one Behemoth remains, value = $$$1$$$.
  • $$$[2]$$$ → value = $$$2$$$.
  • $$$[3]$$$ → value = $$$3$$$.
  • $$$[1,2]$$$: sell the larger Behemoth $$$2$$$ first, leave $$$1$$$ → final attack = $$$1+2=3$$$.
  • $$$[1,3]$$$: sell $$$3$$$ first, leave $$$1$$$ → final attack = $$$1+3=4$$$.
  • $$$[2,3]$$$: sell $$$3$$$ first, leave $$$2$$$ → final attack = $$$2+3=5$$$.
  • $$$[1,2,3]$$$:
    • Step 1: sell $$$3$$$ → remaining sequence $$$[1+3,2+3] = [4,5]$$$.
    • Step 2: sell $$$2$$$ (now $$$5$$$) → add its attack to remaining $$$4$$$, final attack = $$$4+5=9$$$.
    • Thus, the value of this subsequence is $$$9$$$.

Finally, summing all values: $$$1+2+3+3+4+5+9 = 27$$$.