J. Points on the Number Axis A
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is playing a single-player game on the number axis.

There are $$$n$$$ points on the number axis. Each time, the player selects two points. The two points will be removed, and their midpoint will be added. When there is only one point on the axis, the game ends. Formally, if the two chosen points is $$$x_i$$$ and $$$x_j$$$, then $$$\dfrac{x_i+x_j}{2}$$$ will be added after the operation.

In order to play this game happily, Alice will always select two points randomly.

Now Alice have a question: where is the expected position of the last point.

It can be proven that the answer can be expressed in the form $$$\dfrac{p}{q}$$$, you only need to output the value of $$$p\cdot q^{-1} \bmod 998\,244\,353$$$.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line contains $$$n$$$ integers $$$x_i$$$ ($$$0 \le x_1 \le \dots \le x_n \lt 998\,244\,353$$$), denoting the position of the $$$i$$$-th point.

Note that two points may be in the same position.

Output

Output one integer, the answer modulo $$$998\,244\,353$$$.

Example
Input
3
1 2 4
Output
332748120