A. Accelerator
time limit per test
1 с
memory limit per test
512 megabytes
input
standard input
output
standard output

DreamGrid is driving a spaceship from Mars to Earth.

There are $$$n$$$ accelerators on the trajectory to accelerate the spaceship. The $$$i$$$-th accelerator has an accelerating factor of $$$a_i$$$. The spaceship will pass the accelerators one by one. Initially, the velocity of the spaceship is $$$0$$$. When the spaceship passes through an accelerator, it gains energy from the accelerator and the velocity changes. Formally, if the accelerating factor is $$$A$$$ and the velocity before accelerating is $$$v$$$, the velocity after accelerating becomes $$$v'=(v+1)\times A$$$.

However, the $$$n$$$ accelerators are uniformly randomly shuffled. DreamGrid doesn't know the order of the accelerators passed through now. Can you tell him the expected velocity after passing through all the $$$n$$$ accelerators?

It can be proved that the expected velocity is rational. Suppose that the answer can be denoted by $$$\frac{u}{d}$$$ where $$$\gcd(u, d) = 1$$$, you need to output an integer $$$r$$$ such that $$$rd \equiv u\pmod{998\,244\,353}$$$ and $$$0 \le r \lt 998\,244\,353$$$. It can be proved that such $$$r$$$ exists and is unique.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 100\,000$$$), indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 100\,000$$$), indicating the number of accelerators.

The next line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), indicating the accelerating factors.

It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$100\,000$$$.

Output

For each test case output one line containing the integer $$$r$$$.

Example
Input
3
3
1 2 3
1
10
4
5 5 5 5
Output
665496247
10
780
Note

For the first example, there are $$$6$$$ ways to order the accelerators:

  • [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$$$

So the expected velocity is $$$\frac{15+14+12+10+10+9}{3!} = \frac{70}{6}$$$.