Problem Statement

There are $N$ piles of stones and $1$ coin. Initially, the $i\ (1 \le i \le N)$-th pile contains $a_i$ stones.

Using these, $2$ players, Alice and Bob, play a game. When the coin is tossed, heads and tails each come up with probability $\large \frac{1}{2}$.

The game starts with Alice's turn, and the player whose turn it is performs the following operations 1 to 3 in order from the top.

1. Choose $1$ pile that has $1$ or more stones remaining. Suppose the chosen pile has $x$ stones remaining.

2. Declare $1$ integer $k$ satisfying $1 \le k \le x$, then toss the coin. If it comes up heads, remove $k$ stones from the chosen pile. If it comes up tails, do nothing.

3. If operation 2 has resulted in a state where not even $1$ stone remains in any pile, the player whose turn it is wins and the game ends. Otherwise, the turn passes to the opponent.

Find the probability that Alice wins when both Alice and Bob act to maximize their own probability of winning.

It can be proved that the answer can be expressed as an irreducible fraction $\large \frac{p}{q}$ and that there is a unique integer $r$ satisfying $r \times q \equiv p\ (\textrm{mod}\ 998244353)$ and $0 \le r \lt 998244353$. Output this $r$.

Input

$N$
$a_1\ a_2\ \ldots\ a_N$

【Constraints】

• $1 \le N \le 2\times10^5$

• $1 \le a_i \le 10^9$

• All inputs are integers.

Output

Output the answer $\textrm{mod}\ 998244353$.

Sample

1
100

665496236

2
1 1

776412275