K. Yiwen with Formula
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of length $$$n$$$, for any array $$$b$$$ satisfying $$$1 \leq b_i \leq n$$$ and $$$b_1 \lt b_2 \lt \cdots \lt b_k$$$ ($$$k$$$ is the length of $$$b$$$, $$$k \geq 1$$$), calculate:

$$$$$$\prod_{b_1 \lt b_2 \lt \cdots \lt b_k} (a_{b_1}+a_{b_2}+\cdots+a_{b_k})$$$$$$

Input

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10$$$) – the number of test cases.

For each test case:

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), which is the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$0 \leq a_i \leq 10^5$$$), which is the array $$$a$$$.

It is guaranteed that:

  • The sum of $$$n$$$ over all test cases will not exceed $$$2.5 \times 10^5$$$.
  • The sum of $$$a_i$$$ in a single test will not exceed $$$10^5$$$.
  • The sum of $$$a_i$$$ over all test cases will not exceed $$$4\times 10^5$$$.
Output

For each test case, output the result modulo $$$998244353$$$ in a single line.

Example
Input
3
2
1 1
3
1 1 2
5
4 6 9 1 5
Output
2
144
417630946