有一个包含 $N$ 个顶点的无向图。图的顶点编号为 $1$ 到 $N$，每个顶点 $i$ ($1 \le i \le N$) 上写有一个整数 $A_i$。虽然图中初始没有边，但你可以自由添加边。

共有 $2^{\frac{N(N-1)}{2}}$ 种添加边的方式使图成为简单图。请计算每种方式下的 得分 (score)，并求出所有得分之和对 $998244353$ 取模的结果。

• 当图不连通时，得分为 $0$。
• 当图连通时，令 $G$ 为从原图中删去所有桥后得到的图。考虑 $G$ 中每个连通分量上顶点所写整数之和，将这些和相乘，即为该图的得分。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\dots$ $A_N$

• 输入中的所有值均为整数。
• $1 \le N \le 400$
• $0 \le A_i < 998244353$ ($1 \le i \le N$)

输出格式

输出答案。

样例

样例 1

输入

3
8 5 9

输出

1102

样例 2

输入

5
4 2 1 3 10

输出

63860

样例 3

输入

7
229520041 118275986 281963154 784360383 478705114 655222915 970715006

输出

35376232

说明

在第一个样例中，顶点数为 $3$ 的简单连通无向图共有以下 $4$ 种模式：

得分分别为 $360, 360, 360, 22$，因此答案为 $1102$。