题目描述

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$.

输入格式

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 one integer, the answer modulo $998\,244\,353$.

3
1 2 4

332748120