いろはちゃんと算数のテスト

2 secs 1024 MB
morio__'s icon morio__

問題文

いろはちゃんは算数のテストの勉強をしています。

ドリルの問題をすべて解き終わってしまったいろはちゃんは、偶然手元にあったNN個の整数A1,A2,,ANA_1, A_2, \ldots, A_Nを使って自分で問題を作ることにしました。

試行錯誤の末、

  • 11問目は、A1+A2+A3++ANA_1 + A_2 + A_3 + \cdots + A_N
  • 22問目は、A1A2+A3++ANA_1 - A_2 + A_3 + \cdots + A_N
  • 33問目は、A1+A2A3++ANA_1 + A_2 - A_3 + \cdots + A_N
  • \cdots
  • 2N12^{N-1}問目は、A1A2A3ANA_1 - A_2 - A_3 - \cdots - A_N
  • 2N1+12^{N-1} + 1問目は、A2+A1+A3++ANA_2 + A_1 + A_3 + \cdots + A_N
  • 2N1+22^{N-1} + 2問目は、A2A1+A3++ANA_2 - A_1 + A_3 + \cdots + A_N
  • \cdots

のように整数の並びと整数間の加算と減算を変えることで、全部でN!×2N1N! \times 2^{N-1}個もの問題を作ることができました。 意気揚々と解いていたいろはちゃんですが、問題があまりにも多かったため途中で寝てしまいました。

代わりに問題を解いてあげてください。 N!×2N1N! \times 2^{N-1}問も解くと宇宙が滅亡してしまうかもしれないので、代わりに全問題の総和を109+710^9 + 7で割ったあまりを求めてください。

制約

  • 1N1051 \leq N \leq 10^5
  • 0Ai109(1iN)0 \leq A_i \leq 10^9 (1 \leq i \leq N)

入力

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

N
A_1 A_2 ... A_N

出力

答えを出力せよ。出力は標準出力に行い、末尾に改行を入れること。


入出力例1

入力
2
3 7
出力
20

以下の2!×221=42! \times 2^{2-1} = 4問を作りました。これらの和である2020を出力してください。

  • 3+7=103 + 7 = 10
  • 37=43 - 7 = -4
  • 7+3=107 + 3 = 10
  • 73=47 - 3 = 4

入出力例2

入力
3
1 6 8
出力
120

入出力例3

入力
10
31415 9265358 9793238 4626433 832795 0 2884197 169399375 1058209 74944
出力
918888854

109+710^9 + 7で割ったあまりを出力することに注意してください。

Submit


Go (1.21)