Multiset's Subset's Product Sum Easy

2 secs 1024 MB
bayashiko's icon bayashiko

問題文

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

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

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

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

制約

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

入力

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

NN
A1 A2  ANA_1 \ A_2 \ \ldots \ A_N

  

出力

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

  

入力例1

2
3 5

出力例1

23

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

入力例2

3
2 -3 7

出力例2

998244304

2+(3)+(7)+(2×(3))+(2×7)+(3×7)+(2×(3)×7)=23+76+142142=492+(-3)+(7)+(2×(-3))+(2×7)+(-3×7)+(2×(-3)×7)=2-3+7-6+14-21-42=-49 です。
出力するのは 998244353998244353 で割った余りなので、 998244304998244304 が答えです。

入力例3

1
1000000000

出力例3

1755647

Submit


Go (1.21)