杰瑞正在被汤姆追捕！

为了摆脱追捕，杰瑞需要知道有地图有多少个老鼠洞可以隐藏！

但两只鞋太太的家实在太大了，为了简单地说明，定义两个简单无向图 $G_1=(V_1,E_1),G_2=(V_2,E_2)$ 的乘积为一个新的图 $G_1\times G_2=(V^{\ast },E^{\ast })$。

其中新的点集 $V^{\ast }$ 为:

$$V^{\ast }=\left\{(a,b)|a\in V_1,b\in V_2\right\}$$

其中新的边集 $E^{\ast }$ 为：

$$E^{\ast }=\{((u_1,v_1),(u_2,v_2))\mid (u_1,u_2)\in E_1,(v_1,v_2)\in E_2\}$$

对于正整数 $n$，以及给定的图 $G_1,G_2,\dots ,G_n$，两只鞋太太的家可以表示成

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

为了方便逃亡（戏弄汤姆），对于同一个连通块，杰瑞事先打通了所有的老鼠洞，你只需要计算一遍。

为了方便逃亡（戏弄汤姆），对于同一个任何一个连通块，都有老鼠洞。

也就是说，你需要求的是 $H$ 的连通块数量。但是杰瑞忘记了每个 $G_k$ 的具体细节，所以我们现在假设每个 $G_k$ 中任意两点间都有 $\frac{1}{2}$ 的概率连边，求 $H$ 的连通块的期望。显然 $G_k$ 的全体取法共有 $2^{(\genfrac{}{}{0ex}{}{m_1}{2})+(\genfrac{}{}{0ex}{}{m_2}{2})+\cdots +(\genfrac{}{}{0ex}{}{m_n}{2})}$ 种。

方便起见，你只需要输出答案乘以 $2^{(\genfrac{}{}{0ex}{}{m_1}{2})+(\genfrac{}{}{0ex}{}{m_2}{2})+\cdots +(\genfrac{}{}{0ex}{}{m_n}{2})}$，对 $998244353$ 取模即可。

输入格式

第一行输入一个正整数 $n$。

接下来一行输入 $n$ 个正整数,第 $k$ 个正整数为 $m_k$，表示第 $k$ 个图的顶点数量。

输出格式

输出一个整数，表示答案 $mod998244353$。

样例一

input

1
3

output

13

explanation

注意对于 $n=1$ 的情况，就是枚举所有节点个数为$m_1$的带标号无向图的连通块数量之和。

样例二

input

2
2 3

output

73

explanation

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

样例三

input

2
4 4

output

21565

限制与约定

对于所有测试数据，满足 $1\le n,m_k\le {10}^5$。

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$

下载

样例数据下载