题目描述

Bob 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, Bob will always select two adjacent points randomly. Initially, the $i$-th point and the $(i+1)$-th point are adjacent. When Bob added a new point, it inherits its left point's left adjacent point and its right point's right adjacent point.

Now Bob 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$), describing 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

623902723