Multiset's Subset's Product Sum Hard

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

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

• 入力は全て整数 　　

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

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

2
3 5

8
15

3
2 -3 7

6
998244340
998244311

1
1000000000

1755647