問題文

$N$ 個の石の山と $1$ 枚のコインがあります。初め、$i\ (1 \le i \le N)$ 番目の山には $a_i$ 個の石が置いてあります。

これらを用いて、Alice と Bob の $2$ 人がゲームをします。 なお、コインを投げたとき、表と裏がそれぞれ $\large \frac{1}{2}$ の確率で出るものとします。

ゲームは Alice の手番 から始まり、手番のプレイヤーは以下の操作1～3を上から順に行います。

1. 石が $1$ 個以上残っている山を $1$ つ選ぶ。選んだ山に $x$ 個の石が残っているとする。

2. $1 \le k \le x$ を満たす整数 $k$ を $1$ つ宣言した後、コインを投げる。 表が出た場合、選んだ山から $k$ 個の石を取り除く。裏が出た場合、何も行わない。

3. 操作2によって、全ての山に $1$ つも石が残っていない状態になった場合、手番のプレイヤーの勝利とし、ゲームを終了する。 そうでなければ、相手の手番に移る。

Alice も Bob も自分が勝つ確率が最大となるように行動するとき、Alice が勝つ確率を求めてください。

ただし、答えはある既約分数 $\large \frac{p}{q}$ として表わせて、$r \times q \equiv p\ (\textrm{mod}\ 998244353)$ かつ $0 \le r \lt 998244353$ を満たす整数 $r$ が一意に定まることが証明できるので、この $r$ を出力してください。

入力

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

【制約】

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

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

• 入力は全て整数

出力

答えを $\textrm{mod}\ 998244353$ で出力してください。

サンプル

1
100

665496236

2
1 1

776412275