Multiset's Subset's Product Sum Easy

長さが の整数列 が与えられます。

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

ただし、 で の要素数を表します。

• 入力は全て整数 　　

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

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

2
3 5

23

です。

3
2 -3 7

998244304

です。
出力するのは で割った余りなので、 が答えです。

1
1000000000

1755647