ジェリーはトムに追いかけられています！

逃げ切るために、ジェリーは地図上に隠れられるネズミの穴がいくつあるかを知る必要があります！

しかし、トゥーシューズ夫人の家はあまりにも広大です。話を単純にするために、2つの単純無向グラフ $G_{1} =( V_{1} ,E_{1})$ と $G_{2} =( V_{2} ,E_{2})$ の積を新しいグラフ $G_{1} \times G_{2} =\left( V^{*} ,E^{*} \right)$ と定義します。

ここで、新しい頂点集合 $V^{*}$ は以下の通りです。

$$ V^{*} = \left\{{(a,b)| a \in V_{1}, b \in V_{2}}\right\} $$

また、新しい辺集合 $E^{*}$ は以下の通りです。

$$ E^{*} =\left\{\left(( u_{1} ,v_{1}) ,( u_{2} ,v_{2})\right) \mid ( u_{1} ,u_{2}) \in E_{1}, ( v_{1} ,v_{2}) \in E_{2}\right\} $$

正の整数 $n$、および与えられたグラフ $G_{1} ,G_{2} ,\dotsc ,G_{n}$ に対して、トゥーシューズ夫人の家は次のように表されます。

$$ H = (((G_1 \times G_2) \times G_3) \times \cdots) \times G_n $$

逃走（トムをからかうこと）を容易にするため、ジェリーは同じ連結成分内のすべてのネズミの穴をあらかじめつなげており、計算は一度行うだけで済みます。

つまり、求めるべきは $H$ の連結成分の数です。しかし、ジェリーは各 $G_k$ の詳細を忘れてしまいました。そこで、各 $G_k$ において任意の2点間に辺が存在する確率を $\frac12$ と仮定し、$H$ の連結成分数の期待値を求めます。明らかに、$G_k$ の取り方は全部で ${\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}}$ 通り存在します。

便宜上、答えに ${\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}}$ を掛け、それを $998244353$ で割った余りを出力してください。

入力

1行目に正の整数 $n$ が入力されます。

続く1行に $n$ 個の正の整数が入力され、$k$ 番目の整数 $m_k$ は $k$ 番目のグラフの頂点数を示します。

出力

答えを $998244353$ で割った余りを整数で出力してください。

入出力例

入力 1

1
3

出力 1

13

注記 1

$n=1$ の場合、頂点数 $m_1$ のラベル付き無向グラフにおける連結成分数の総和を求めることと同義であることに注意してください。

入力 2

2
2 3

出力 2

73

注記 2

$G_1$ に辺が $0$ 本ある場合、どのような $G_2$ であっても $H$ には $6$ 個の連結成分が存在し、そのような構成は $8$ 通りあります。

$G_1$ に辺が $1$ 本、$G_2$ に辺が $0$ 本ある場合、$H$ には $6$ 個の連結成分が存在し、そのような構成は $1$ 通りあります。

$G_1$ に辺が $1$ 本、$G_2$ に辺が $1$ 本ある場合、$H$ には $4$ 個の連結成分が存在し、そのような構成は $3$ 通りあります。

$G_1$ に辺が $1$ 本、$G_2$ に辺が $2$ 本ある場合、$H$ には $2$ 個の連結成分が存在し、そのような構成は $3$ 通りあります。

$G_1$ に辺が $1$ 本、$G_2$ に辺が $3$ 本ある場合、$H$ には $1$ 個の連結成分が存在し、そのような構成は $1$ 通りあります。

$$ 6\times 8 + 6\times 1 + 4\times 3 + 2\times 3 + 1\times 1 = 73 $$

入力 3

2
4 4

出力 3

21565

制約

すべてのテストデータにおいて、$1\le n, m_k\le 10^5$ を満たします。