D. Attraction Theory
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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$$$.

Example
Input
7
1
1
2
5 10
3
1 1 1
4
1 1 1 1
4
10 2 9 7
5
1000000000 1000000000 1000000000 1000000000 1000000000
8
100 2 34 59 34 27 5 6
Output
1
45
24
72
480
333572930
69365
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$$$.