問題文
長さ N の数列 A があります。この数列をいくつかの連続部分列に分割することを考えます。このとき、分割個数を K とすると K 個の連続部分列 B1,B2,…,BK は以下の条件を満たしていなければいけません。
- B1,B2,…,BK はいずれも A の空でない連続部分列である。
- B1,B2,…,BK をこの順序で連結すると A となる。
ある分割のスコアは i=1∑Kj=1∑Li(−1)i+1Bi,j と定義されます。ここで Li は Bi の長さです。
考えられる分割方法は 2N−1 通りありますが、それらすべてに対するスコアの総和を 109+7 で割ったあまりを求めてください。
制約
- 入力はすべて整数
- 1≤N≤2×105
- 1≤Ai≤109
入力
出力
答えを出力し、最後に改行してください。
入力例1
出力例1
考えられる分割方法は ((1,2,3)),((1,2),(3)),((1),(2,3)),((1),(2),(3)) の 4 通りです。
スコアは順に 6,0,−4,2 なのでそれらの総和である 4 を出力します。
入力例2
15
986443860 261815926 135792421 423098417 667797511 192154129 543455015 87493239 690182347 484865424 916005028 320032940 811507723 438422973 753096704
出力例2