F. Ranking Random Pick
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For an array $$$b$$$ of length $$$l$$$, a ranking random pick is defined as follows: from the non-decreasing sorted version of array $$$b$$$ (denoted as array $$$c$$$), exactly one element is selected, where the probability of selecting $$$c_i$$$ is given by $$$\frac{i}{1 + 2 + \dots + l}$$$.

Alice and Bob have an array $$$a$$$ of length $$$n$$$ and a fair coin. Initially, Alice's score is $$$0$$$.

If array $$$a$$$ is non-empty, the coin is flipped:

  • If the coin shows heads, Bob performs a ranking random pick from $$$a$$$ and removes the selected element from $$$a$$$.
  • If the coin shows tails, Alice performs a ranking random pick from $$$a$$$, adds the value of the selected element to her score, and removes all elements from $$$a$$$.

Calculate the expected value of Alice's score. Output the answer modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 400$$$). The description of the test cases follows.

  • The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$);
  • The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, print a single integer — the answer to the problem modulo $$$998\,244\,353$$$.

Example
Input
3
1
2
2
3 5
5
1000000000 999999999 999999999 1000000000 999999998
Output
1
582309209
588585275
Note

In the first case, Alice has $$$\frac{1}{2}$$$ probability of getting a score of $$$2$$$, and $$$\frac{1}{2}$$$ probability of getting a score of $$$0$$$, so the expected score for Alice is $$$\frac{1}{2} \times 2+\frac{1}{2}\times 0=1$$$.

In the second case, Alice's expected score is $$$\frac{1}{2}\times\frac{1}{3} \times 3+\frac{1}{2}\times\frac{2}{3} \times 5+\frac{1}{2}\times\frac{1}{3} \times \frac{1}{2}\times5+\frac{1}{2}\times\frac{2}{3} \times \frac{1}{2}\times3=\frac{37}{12}$$$.

The game tree for the second case.