Problem Description

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

$$\prod_{b_1<b_2<\cdots<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.

3
2
1 1
3
1 1 2
5
4 6 9 1 5

2
144
417630946