Expected Last Point

Bob is playing a single‐player game on the number axis. Initially, there are \(n\) points with positions \(a_1,a_2,\dots,a_n\) (given in order from left to right). In each move, Bob randomly selects two adjacent points, say \(x_i\) and \(x_j\) (with \(x_j\) immediately to the right of \(x_i\)), removes them, and inserts a new point at their midpoint \(\frac{x_i+x_j}{2}\). The new point inherits the adjacent neighbors of the removed points, preserving the order. The game ends when there is only one point remaining.

It can be proven that the expected final position can be expressed as a rational number \(\frac{p}{q}\). You are required to compute \(p \cdot q^{-1} \bmod 998\,244\,353\).

Hint: It turns out that the expected final value can be written as a linear combination of the initial positions:

[ E = \frac{1}{4^{n-1}}\sum_{i=1}^{n} \binom{2(i-1)}{i-1}\binom{2(n-i)}{n-i},a_i. ]

You need to compute the value of \(E\) modulo \(998\,244\,353\).

inputFormat

The first line contains a single integer \(n\) (\(2 \le n \le 2 \cdot 10^5\)), the number of points.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)), representing the positions of the points in order.

outputFormat

Output a single integer, the expected final position \(E\) computed as \(p \cdot q^{-1} \bmod 998\,244\,353\).

sample

2
0 10

5