Jerry is being chased by Tom!

To escape, Jerry needs to know how many mouse holes there are in the map to hide in!

However, Mammy Two-Shoes' house is too large. To simplify, we define the product of two simple undirected graphs $G_{1} =( V_{1} ,E_{1})$ and $G_{2} =( V_{2} ,E_{2})$ as a new graph $G_{1} \times G_{2} =\left( V^{*} ,E^{*} \right)$.

The new vertex set $V^{*}$ is:

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

The new edge set $E^{*}$ is:

$$ 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\} $$

For a positive integer $n$ and given graphs $G_{1} ,G_{2} ,\dotsc ,G_{n}$, Mammy Two-Shoes' house can be represented as:

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

For the purpose of escaping (and teasing Tom), Jerry has already connected all mouse holes within the same connected component, so you only need to count them once.

Every connected component contains mouse holes.

In other words, you need to find the number of connected components in $H$. However, Jerry has forgotten the specific details of each $G_k$. We now assume that for each $G_k$, there is a $\frac{1}{2}$ probability of an edge existing between any two vertices. Find the expected number of connected components in $H$. Clearly, there are ${\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}}$ total ways to choose all $G_k$.

For convenience, you only need to output the answer multiplied by ${\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}}$, modulo $998244353$.

Input

The first line contains a positive integer $n$.

The next line contains $n$ positive integers, where the $k$-th integer is $m_k$, representing the number of vertices in the $k$-th graph.

Output

Output an integer representing the answer $\bmod 998244353$.

Examples

Input 1

1
3

Output 1

13

Note 1

Note that for the case $n=1$, this is the sum of the number of connected components over all labeled undirected graphs with $m_1$ vertices.

Input 2

2
2 3

Output 2

73

Note 2

If $G_1$ has $0$ edges, any $G_2$ will result in $6$ connected components in $H$; there are $8$ such scenarios.

If $G_1$ has $1$ edge and $G_2$ has $0$ edges, $H$ has $6$ connected components; there is $1$ such scenario.

If $G_1$ has $1$ edge and $G_2$ has $1$ edge, $H$ has $4$ connected components; there are $3$ such scenarios.

If $G_1$ has $1$ edge and $G_2$ has $2$ edges, $H$ has $2$ connected components; there are $3$ such scenarios.

If $G_1$ has $1$ edge and $G_2$ has $3$ edges, $H$ has $1$ connected component; there is $1$ such scenario.

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

Input 3

2
4 4

Output 3

21565

Constraints

For all test cases, $1\le n, m_k\le 10^5$.