問題文

競プロで有名な素数といえば $998244353$ ですが、実は $999630629$ も素数です。 問題文中にこの $2$ つの素数が出てくるので注意してください。

長さ $N$ の整数列 $A$ が与えられます。また $ \lbrace 1,2, \dots , N \rbrace$ の空でない部分集合 $S$ に対して $f(S)$ を次のように定めます。

　$f(S)= \left( \displaystyle \sum_{i \in S} A_i \right )\ \mathrm{mod} \ 999630629$

$\lbrace 1,2,\dots , N \rbrace$ の空でない部分集合 $S$ は $2^N-1$ 個ありますが、その全てに対して $f(S)$ を求め、その総和を $998244353$ で割った余りを求めてください。

（答えも $999630629$ で割るのではないことに注意してください。）

入力

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

出力

$f(S)$ の総和を $998244353$ で割った余りを求めてください。

サンプル

2
3 5

16

1
1 

1

6
1 2 3 4 5 6

672