Multiset's Subset's Product Sum Hard

2 secs 1024 MB
bayashiko

問題文


長さが の整数列 が与えられます。 それぞれについて、以下の問題を解いてください。

問題

集合 の要素数が の部分集合 として考えられるもの全てに対して以下の値を求め、その総和を で割った余りを出力してください。

制約


  • 入力は全て整数   

入力


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


  

出力


個の整数を改行区切りで出力してください。ここで、 番目の整数は の問題に対する答えとなります。

  

入力例1


2
3 5

出力例1


8
15

入力例2


3
2 -3 7

出力例2


6
998244340
998244311

入力例3


1
1000000000

出力例3


1755647

Submit


Go (1.14)