16:05 部分点のテストデータは全て正しいのですが, テストデータが不完全であるかもしれないという情報を先に提示していたので, G 問題の部分点もコンテストの得点の対象外とさせていただきます.誤解を招く表記をしてしまい申し訳ありません.

15:46 現在のデータにミスが有ることが発覚しました. 部分点のケースの投稿は可能ですが, G 問題はコンテストの得点対象外とさせてください. 報告が遅くなってしまい, 大変申し訳ありませんでした.

13:55 現在のデータは「昨日の深夜に問題が発覚した後，japlj が寝ぼけ眼で必死に作りなおして一切チェックされていないデータ」です．今はこのデータの正当性をチェックしているところですが，ほぼ眠りかけの japlj の書いたコードを信じる人は提出してもいいかもしれません．（オススメしません）

13:00 開催前日の夜になって G 問題のテストデータの不備が発覚した運営！果たしてコンテスト中に正しいテストデータに差し替えることはできるのか！？！？スタッフの活躍に乞うご期待！！！！！（すみません，データ直るまで提出しないでください）

問題文

ミズゴロ王国のカガミズ王は出る杭を打つのが大好きです．毎日のように家来を一列に並べては，渾身のハイドロポンプで出っぱっている人の身長を縮めて楽しんでいます．

カガミズ王の側近であるあなたは，王がハイドロポンプの餌食とする家来を選ぶときに，単に身長が高い人を選んでいるわけではないことに気がつきました．

王いわく，「何につけてもこの世は中庸が肝心である．端にいない者は誰でも，その身長が両隣の者の身長の平均と同じでなければならないのだ」と．

こうしてカガミズ王はひとしきりハイドロポンプを放った後，皆の身長がその両隣の人の身長の平均と等しくなっているような家来の列を見て悦に入るのでした．

さて，あなたはこの様子を毎日のように見ていてあることを考えました．王が満足するような身長の並びとは何通りぐらいあるのだろうか．条件がこれだけだと無尽蔵に場合があると考えたあなたは，それぞれの場所にいる家来の身長に上限と下限を設けて数えることにしました．

ちなみにミズゴロ王国では人の身長はなぜか必ず整数で，よくわかりませんが身長が 0 だったり負だったりする人もいます．

課題

N 要素の整数列 A, B が与えられる．以下の条件を満たす N 要素の整数列 X は何通りあるか．答えを 1,000,000,007 (= 10^9 + 7) で割ったあまりを求めよ．

• i = 1, ..., N に対し A_i ≦ X_i ≦ B_i．
• i = 2, ..., N - 1 に対し X_i = \frac{X_{i-1} + X_{i+1}}{2}．

制約

すべての入力データは以下の制約を満たす．

• 3 ≦ N ≦ 10^5．
• -10^9 ≦ A_i ≦ B_i ≦ 10^9．

また，この問題には部分点が設定されており，2 点分の入力データは追加で以下の制約を満たす．

• N ≦ 100．
• -100 ≦ A_i ≦ B_i ≦ 100．

入力例 1

3
0 0 0
2 2 2

出力例 1

5

• X_1 = 0,\ X_2 = 0,\ X_3 = 0
• X_1 = 0,\ X_2 = 1,\ X_3 = 2
• X_1 = 1,\ X_2 = 1,\ X_3 = 1
• X_1 = 2,\ X_2 = 1,\ X_3 = 0
• X_1 = 2,\ X_2 = 2,\ X_3 = 2

の 5 つが条件を満たす数列である.

入力例 2

8
-9 -8 -7 -6 -8 -20 -9 -1
6 8 10 16 42 18 14 20

出力例 2

42

入力例 3

3
-1000000000 -1000000000 -1000000000
1000000000 1000000000 1000000000

出力例 3

85

この条件を満たす数列は 2,000,000,002,000,000,001 通りある. 通り数を1,000,000,007 で割ったあまりを出力することに注意せよ.