408444: GYM103119 A Accelerator
Description
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 < 998\,244\,353$$$. It can be proved that such $$$r$$$ exists and is unique.
InputThere 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$$$.
OutputFor each test case output one line containing the integer $$$r$$$.
ExampleInput3 3 1 2 3 1 10 4 5 5 5 5Output
665496247 10 780Note
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}$$$.