F. Who Will Witness the End?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Before her final sortie, Chtholly asks Willem three questions.

The third is this: when the end finally comes, who will remain to witness it?

Willem cannot answer her directly. Instead, he draws a circle on the board, calling it the ring of all things, and writes down $$$n$$$ labeled integers $$$a_1,a_2,\ldots,a_n$$$. Every possible order around the ring describes a different way in which the world might reach its end.

Consider a permutation $$$p_1,p_2,\ldots,p_n$$$ of the integers from $$$1$$$ to $$$n$$$. Place the corresponding numbers on a circle in this order. The weight of the resulting circular arrangement is

$$$$$$ \prod_{i=1}^{n}(a_{p_i}+a_{p_{i+1}}), $$$$$$

where $$$p_{n+1}=p_1$$$.

Two permutations describe the same circular arrangement if one can be obtained from the other by a cyclic shift. Reversing an arrangement does not make it the same arrangement; in other words, reflected arrangements are considered different unless they also coincide after a cyclic shift.

Find the sum of the weights of all distinct circular arrangements. Since the answer may be large, output it modulo $$$998\,244\,353$$$.

Input

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

The first line of each test case contains one integer $$$n$$$ ($$$3 \le n \le 2\cdot 10^5$$$) — the number of labeled integers.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt 998\,244\,353$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output one integer — the sum of the weights of all distinct circular arrangements, modulo $$$998\,244\,353$$$.

Example
Input
3
3
1 2 3
6
0 1 0 1 0 1
10
114514 1919810 350234 11831 314159265 271828182 123456789 998244352 5201314 23333333
Output
120
12
265885269
Note

In the first test case, there are two distinct circular arrangements. They can be represented by the permutations $$$[1,2,3]$$$ and $$$[1,3,2]$$$. Both have weight

$$$$$$ (1+2)(2+3)(3+1)=60, $$$$$$

so the answer is $$$120$$$.

In the second test case, an arrangement has nonzero weight only if zeros and ones alternate around the circle. There are

$$$$$$ \frac{2\cdot3!\cdot3!}{6}=12 $$$$$$

such circular arrangements: the factor $$$2$$$ chooses whether a linear representative starts with a zero or a one, and division by $$$6$$$ identifies cyclic shifts. Each arrangement has weight $$$1$$$. All other arrangements have weight $$$0$$$, so the answer is $$$12$$$.