問題文
いろはちゃんは算数のテストの勉強をしています。
ドリルの問題をすべて解き終わってしまったいろはちゃんは、偶然手元にあったN個の整数A1,A2,…,ANを使って自分で問題を作ることにしました。
試行錯誤の末、
- 1問目は、A1+A2+A3+⋯+AN
- 2問目は、A1−A2+A3+⋯+AN
- 3問目は、A1+A2−A3+⋯+AN
- ⋯
- 2N−1問目は、A1−A2−A3−⋯−AN
- 2N−1+1問目は、A2+A1+A3+⋯+AN
- 2N−1+2問目は、A2−A1+A3+⋯+AN
- ⋯
のように整数の並びと整数間の加算と減算を変えることで、全部でN!×2N−1個もの問題を作ることができました。
意気揚々と解いていたいろはちゃんですが、問題があまりにも多かったため途中で寝てしまいました。
代わりに問題を解いてあげてください。
N!×2N−1問も解くと宇宙が滅亡してしまうかもしれないので、代わりに全問題の総和を109+7で割ったあまりを求めてください。
制約
- 1≤N≤105
- 0≤Ai≤109(1≤i≤N)
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。出力は標準出力に行い、末尾に改行を入れること。
入出力例1
以下の2!×22−1=4問を作りました。これらの和である20を出力してください。
- 3+7=10
- 3−7=−4
- 7+3=10
- 7−3=4
入出力例2
入出力例3
入力
10
31415 9265358 9793238 4626433 832795 0 2884197 169399375 1058209 74944
109+7で割ったあまりを出力することに注意してください。