問題文
長さが N の整数列 A=(A1,A2,…,AN) が与えられます。
集合 S={1,2,…,N} の空でない部分集合 T={t1,t2,…,tsize(T)} として考えられるものは全部で 2N−1 個ありますが、その全てに対して以下の値を求め、その総和を 998244353 で割った余りを出力してください。
- ∏i=1size(T)Ati
ただし、 size(T) で T の要素数を表します。
制約
- 1≤N≤105
- −109≤Ai≤109
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
出力
答えを出力してください。
入力例1
出力例1
3+5+(3×5)=23 です。
入力例2
出力例2
2+(−3)+(7)+(2×(−3))+(2×7)+(−3×7)+(2×(−3)×7)=2−3+7−6+14−21−42=−49 です。
出力するのは 998244353 で割った余りなので、 998244304 が答えです。
入力例3
出力例3