Multiset's Subset's Product Sum Easy

問題文

長さが $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。

集合 $S=\{1,2,\ldots,N\}$ の空でない部分集合 $T=\{t_1,t_2,\ldots,t_{size(T)}\}$ として考えられるものは全部で $2^N-1$ 個ありますが、その全てに対して以下の値を求め、その総和を $998244353$ で割った余りを出力してください。

• $\prod_{i=1}^{size(T)} A_{t_i}$

ただし、 $size(T)$ で $T$ の要素数を表します。

制約

• $1\leq N \leq 10^5$
• $-10^9 \leq A_i \leq 10^9$
• 入力は全て整数 　　

入力

入力は以下の形式で標準入力から与えられます。

出力

答えを出力してください。

入力例1

2
3 5

出力例1

23

$3+5+(3×5)=23$ です。

入力例2

3
2 -3 7

出力例2

998244304

$2+(-3)+(7)+(2×(-3))+(2×7)+(-3×7)+(2×(-3)×7)=2-3+7-6+14-21-42=-49$ です。
出力するのは $998244353$ で割った余りなので、 $998244304$ が答えです。

入力例3

1
1000000000

出力例3

1755647