Expected Last Point on the Number Axis

Alice is playing a single-player game on the number axis. There are \( n \) points on the axis. In each move, she randomly selects two points \( x_i \) and \( x_j \), removes them, and adds a new point at their midpoint \( \frac{x_i + x_j}{2} \). The process is repeated until only one point remains. It can be proven that the expected position of the last point is equal to the average of the initial points.

Your task is to compute the expected value of the last point. Since the answer can be expressed as a rational number \( \frac{p}{q} \), output \( p \cdot q^{-1} \bmod 998\,244\,353 \), where \( q^{-1} \) denotes the modular inverse of \( q \) modulo \( 998\,244\,353 \).

Note: The modular inverse exists because \( 998\,244\,353 \) is a prime number.

inputFormat

The first line contains a single integer \( n \) (\( 1 \leq n \leq 10^5 \)), the number of points. The second line contains \( n \) space-separated integers \( x_1, x_2, \dots, x_n \) (\( -10^9 \leq x_i \leq 10^9 \)) representing the positions of the points on the number axis.

outputFormat

Output a single integer, which is the value of \( p \cdot q^{-1} \bmod 998\,244\,353 \), representing the expected position of the last point.

sample

1
5

5