問題文

長さ$N$の数列$A$が与えられます。$A$の空でない部分集合は$2^N - 1$通りありますが、それぞれについて値の平均を計算し、それらの総和を$mod998244353$で求めてください。

制約

• $1 \leq N \leq 2 \times10^5$
• $1 \leq A_{i} \leq 10^9$

入力

入力はすべて整数である。

N
A_1 A_2 ... A_N

出力

計算結果を一行に出力せよ。

サンプル

3
1 2 3

14

$A$の空でない部分集合は$\{1\}$,$\{2\}$,$\{3\}$,$\{1,2\}$,$\{1,3\}$,$\{2,3\}$,$\{1,2,3\}$の7つです。 値の平均はそれぞれ$1$,$2$,$3$,$\frac{3}{2}$,$2$,$\frac{5}{2}$,$2$です。これらの総和である14が答えとなります。

5
10 2 3 6 4

155

15
611609221 130604016 908556959 572844438 421449617 876143797 451739574 696504047 748732603 977231473 518897757 385226840 772638935 726395840 625232881

731794120