J. Disjoint-Set-Union Sum
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Boboge has an array $$$a$$$ with $$$n$$$ numbers in a line. In the beginning, each number forms a set. Then Boboge will do the following merging operation $$$n-1$$$ times:

Pick up two adjacent sets, merge them, and add the value of the new set into $$$ans$$$. The value of a set is the sum of numbers in it.

After $$$n-1$$$ merging operations, exactly one set will be left.

A set can be represented in an interval $$$[l, r]$$$ of the original array. Two sets $$$i, j(l_i \lt l_j)$$$ are adjacent if and only if $$$r_i=l_j-1$$$. Note that the same numbers can be in one set.

Now Boboge wants to know the $$$\sum{ans}$$$ for all possible merging ways.

Input

The first consists of a single integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the array's length.

The second line consists of $$$n$$$ integers $$$a_1, a_2,\dots,a_{n-1},a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the array.

Output

Output a single integer — the answer.

As the answer may be very large, print it modulo $$$998244353$$$.

Examples
Input
3
1 2 3
Output
20
Input
6
1 1 4 5 1 4
Output
5710
Input
10
689908266 691306300 127791789 650024903 820790283 179240641 548340689 541264423 994511361 993667526
Output
792245278
Note

For the first example, There are two possible ways of merging.

1. $$$[1],[2],[3] \rightarrow [1, 2], [3] \rightarrow [1, 2, 3]$$$, the $$$ans$$$ of this order is $$$3+6=9$$$.

2. $$$[1],[2],[3] \rightarrow [1], [2, 3] \rightarrow [1, 2, 3]$$$, the $$$ans$$$ of this order is $$$5+6=11$$$.

$$$\sum{ans} = 20$$$.