問題文

N 頂点の無向グラフがあります。このグラフの頂点には 1 から N までの番号がつけられており、頂点 i\ (1 \le i \le N) には整数 A_i が書かれています。このグラフには辺がありませんが、あなたが自由に辺を張ることができます。

このグラフが単純グラフとなるような辺の張り方は 2^{\frac{N(N-1)}{2}} 通り存在しますが、そのすべてについて以下の スコア を計算し、その総和を 998244353 で割った余りを求めてください。

• グラフが連結でないとき、その スコア は 0 である。
• グラフが連結なとき、グラフから橋である辺を取り除いたグラフを G とする。G の各連結成分について頂点に書かれた整数の和を考え、その総積を スコア とする。

制約

• 1 \le N \le 400
• 0 \le A_i \lt 998244353\ (1 \le i \le N)
• 入力はすべて整数

入力例 1

3
8 5 9

出力例 1

1102

3 頂点の単純連結無向グラフは、次の 4 通りです。

スコアは左からそれぞれ 360, 360, 360, 22 なので、答えは 1102 です。

入力例 2

5
4 2 1 3 10

出力例 2

63860

入力例 3

7
229520041 118275986 281963154 784360383 478705114 655222915 970715006

出力例 3

35376232

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