Derenville and Soyluland, the noble ally nations, are at war with tough opponents! People of Derenville need resources. So caravans are sent from Soyluland's capital to Derenville's capital.

The path between their capital cities can be considered as a single line and there are \(\mathbf{N-1}\) cities on the way (excluding the capitals). Some of these cities have resting locations for caravans to stop and have a rest. Soyluland's capital is at index 0 and Derenville's capital is at index \(\mathbf{N}\). The distance between each consecutive city is 1 unit.

Traveling for a long time is difficult. So the difficulty of traveling from one city to the next increases as the caravans proceed. If the caravans traveled \(\mathbf{k}\) units after the last rest, the difficulty of covering the \(\mathbf{k+1}\)-st unit will have the cost \(\mathbf{a_{k+1}}\). When the caravans rest in a city, the cost of going to the next city will be \(\mathbf{a_1}\) and so on. It is guaranteed that for each \(\mathbf{k}\) \(\in\) \([\mathbf{1}, \mathbf{N-1}]\), \(\mathbf{a_k}\) \(\leq\) \(\mathbf{a_{k+1}}\). The difficulty of the travel is calculated by summing up the difficulties of each unit traveled in the journey.

For instance, if \(\mathbf{N}\) = 4 and there is a rest location at the 3rd city, the cost will be \(\mathbf{2a_1} + \mathbf{a_2} + \mathbf{a_3}\). Because the cost of going to the city #3 is \(\mathbf{a_1 + a_2 + a_3}\). Then the caravans rest in city #3. Now the cost of going to the 4th from the 3rd will be \(\mathbf{a_1}\).

Strategists of Dereville and Soyluland do not know which cities contain rest sites and they want to know the expected value \(\mathbf{E}\) of the difficulty of a travel. The expected value is calculated by summing up the product of difficulties of distributions with their probabilities.

There will be \(\mathbf{2^{N-1}}\) different distributions of rest locations. Two distributions are considered different if there is a city such that it includes a rest location in only one of these distributions. All of the distributions are equiprobable. Since \(\mathbf{E\cdot2^{N-1}}\) is an integer, your task is to print \(\mathbf{E\cdot2^{N-1}}\) modulo 998244353.

Input:

The first line contains a single integer \(\mathbf{N}\), the distance between Soyluland's capital and Derenville's capital.

The second line will contain exactly \(\mathbf{N}\) integers, the costs of traveling the \(k\)th unit \(\mathbf{a_1, a_2,...,a_N}\).

\(1 \leq N \leq 10^6\\\)

\(1 \leq a_1 \leq a_2 \leq ... \leq a_N \leq 10^6\)

Output:

You should print one number, \(\mathbf{E\cdot2^{N-1}}\), modulo 998244353.

Examples:

Input 1:

2
1 2

Output 1:

5

Input 2:

4
1 3 3 7

Output 2:

60

Explanation:

In the first sample input, \(\mathbf{N}\) is 2 and there are \(\mathbf{2^{N-1}}\) = 2 different distributions. City #1 may accommodate a rest location or not. Both distributions have probabilities \(0.5\). If there is a rest location in city #1, the difficulty will be \(\mathbf{a_1+a_1}\) = 2. If there is not, the difficulty will be \(\mathbf{a_1+a_2}\) = 3. Looking at these, we see that the expected value \(\mathbf{E}\) is \(0.5 \cdot 2 + 0.5 \cdot 3\). The answer (\(\mathbf{E\cdot2^{N-1}}\)) will be \(\mathbf{2 \cdot E}\) = 5. In the second sample, there are 8 equiprobable distributions: ---, --+, -+-, -++, +--, +-+, ++-, +++ (- represents that there is no rest site at that respective city, + represents that there is a rest site at that city). The difficulties of travels will be 14, 8, 8, 6, 8, 6, 6, 4 respectively. The expected value will be \(14\cdot\frac{1}{8}\) + \(8\cdot\frac{1}{8}\) + \(8\cdot\frac{1}{8}\) + \(6\cdot\frac{1}{8}\) + \(8\cdot\frac{1}{8}\) + \(6\cdot\frac{1}{8}\) + \(6\cdot\frac{1}{8}\) + \(4\cdot\frac{1}{8}\). So \(\mathbf{E\cdot2^{N-1}}\) will be 60.