Description

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 Format

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 < 998\,244\,353$), denoting the position of the $i$-th point.

Note that two points may be in the same position.

Output Format

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

3
1 2 4

332748120