Sum of Averages (subset)

2 secs 1024 MB
yunipoke's icon yunipoke

問題文

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

制約

  • 1N2×1051 \leq N \leq 2 \times10^5
  • 1Ai1091 \leq A_{i} \leq 10^9

入力

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

N
A_1 A_2 ... A_N

出力

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

サンプル

入力1
3
1 2 3
出力1
14

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

入力2
5
10 2 3 6 4
出力2
155
入力3
15
611609221 130604016 908556959 572844438 421449617 876143797 451739574 696504047 748732603 977231473 518897757 385226840 772638935 726395840 625232881
出力3
731794120

Submit


Go (1.21)