Yiwen with Formula

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.

Sample Input

3

2

1 1

3

1 1 2

5

4 6 9 1 5

Sample Output

2

144

417630946

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（7）