数列分割ふたたび

2 secs 1024 MB
first_vil's icon first_vil

問題文

長さ NN の数列 AA があります。この数列をいくつかの連続部分列に分割することを考えます。このとき、分割個数を KK とすると KK 個の連続部分列 B1,B2,,BKB_1,B_2,\dots,B_K は以下の条件を満たしていなければいけません。

  • B1,B2,,BKB_1,B_2,\dots,B_K はいずれも AA の空でない連続部分列である。
  • B1,B2,,BKB_1,B_2,\dots,B_K をこの順序で連結すると AA となる。

ある分割のスコアは i=1Kj=1Li(1)i+1Bi,j\displaystyle \sum_{i=1}^{K}\sum_{j=1}^{L_i}(-1)^{i+1} B_{i,j} と定義されます。ここで LiL_iBiB_i の長さです。

考えられる分割方法は 2N12^{N-1} 通りありますが、それらすべてに対するスコアの総和を 109+710^9+7 で割ったあまりを求めてください。

制約

  • 入力はすべて整数
  • 1N2×1051 \le N \le 2 \times 10^5
  • 1Ai1091 \le A_i \le 10^9

入力

NN
A1 A2  ANA_1\ A_2\ \dots\ A_N

出力

答えを出力し、最後に改行してください。

入力例1

3
1 2 3

出力例1

4

考えられる分割方法は ((1,2,3)),((1,2),(3)),((1),(2,3)),((1),(2),(3))((1,2,3)),((1,2),(3)),((1),(2,3)),((1),(2),(3))44 通りです。 スコアは順に 6,0,4,26,0,-4,2 なのでそれらの総和である 44 を出力します。

入力例2

15
986443860 261815926 135792421 423098417 667797511 192154129 543455015 87493239 690182347 484865424 916005028 320032940 811507723 438422973 753096704

出力例2

896089113

Submit


Go (1.21)