Taylor Swift - Love Story (Taylor's Version)⠀

There are $n$ people in positions $p_1, p_2, \ldots, p_n$ on a one-dimensional coordinate axis. Initially, $p_i = i$ for each $1 \leq i \leq n$.

You can introduce an attraction at some integer coordinate $x$ ($1 \le x \le n$), and then all the people will move closer to the attraction to look at it.

Formally, if you put an attraction in position $x$ ($1 \le x \le n$), the following changes happen for each person $i$ ($1 \le i \le n$):

• if $p_i = x$, no change;
• if $p_i \lt x$, the person moves in the positive direction, and $p_i$ is incremented by $1$;
• if $p_i \gt x$, the person moves in the negative direction, and $p_i$ is decremented by $1$.

You can put attractions any finite number of times, and in any order you want.

It can be proven that all positions of a person always stays within the range $[1, n]$, i.e. $1 \le p_i \le n$ at all times.

Each position $x$ ($1 \le x \le n$), has a value $a_x$ associated with it. The score of a position array $[p_1, p_2, \ldots, p_n]$, denoted by $score(p)$, is $\sum_{i = 1}^{n} a_{p_i}$, i.e. your score increases by $a_x$ for every person standing at $x$ in the end.

Over all possible distinct position arrays $p$ that are possible with placing attractions, find the sum of $score(p)$. Since the answer may be large, print 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 a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line of each test case contains $n$ integers — $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$)

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 a single line containing an integer: the sum of $score(p)$ over all possible distinct position arrays $p$ that are possible with placing attractions, modulo $998\,244\,353$.

Note

In the first test case, the only possible result is that person $1$ stays at $1$. The score of that is $a_1 = 1$.

In the second test case, the following position arrays $[p_1, p_2]$ are possible:

• $[1, 2]$, score $15$;
• $[1, 1]$, score $10$;
• $[2, 2]$, score $20$.

The sum of scores is $15 + 10 + 20 = 45$.

In the third test case, the following position arrays $[p_1, p_2, p_3]$ are possible:

• $[1, 1, 1]$;
• $[1, 1, 2]$;
• $[1, 2, 2]$;
• $[1, 2, 3]$;
• $[2, 2, 2]$;
• $[2, 2, 3]$;
• $[2, 3, 3]$;
• $[3, 3, 3]$.

Each has a score of $3$, and thus the total sum is $24$.