题目描述

高さ $10^9$ マス，幅 $N$ マスのグリッドを考え，左から $i(1\ \leq\ i\ \leq\ N)$ 番目，下から $j(1\ \leq\ j\ \leq\ 10^9)$ 番目のマス目を $(i,\ j)$ と表すことにします。

すぬけ君は各 $i\ =\ 1,\ 2,\ ...,\ N$ について，左から $i$ 列目のマスたちを，下から $h_i$ 個を残すように切り取りました。 そして赤，青の絵の具を使い，マス目を絵の具で塗ります。 以下の条件を満たすような塗り分け方は何通りか求めて下さい。ただし答えは非常に大きくなるので，$10^9+7$ で割った余りを出力して下さい。

• 全ての(切り取った後に残された)マスたちは，赤，青のどちらかの色に塗られている。
• 全ての $1\ \leq\ i\ \leq\ N-1$, $1\ \leq\ j\ \leq\ min(h_i,\ h_{i+1})-1$ について，$(i,\ j),\ (i,\ j+1),\ (i+1,\ j),\ (i+1,\ j+1)$ の4マスのなかにちょうど $2$ 個ずつ赤色と青色のマスが存在する。

输入格式

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

$N$ $h_1$ $h_2$ $...$ $h_N$

输出格式

塗り分け方の個数を $10^9+7$ で割った余りを出力せよ。

题目大意

给定 $N$ 列的网格，每列高为 $h_i$，将每个格子染色成红色或蓝色，使得每个 $2\times2$ 的区域都恰好有两个蓝格子和两个红格子，求方案数。

9
2 3 5 4 1 2 4 2 1

12800

2
2 2

6

5
2 1 2 1 2

256

9
27 18 28 18 28 45 90 45 23

844733013

提示

制約

• $1\ \leq\ N\ \leq\ 100$
• $1\ \leq\ h_i\ \leq\ 10^9$

Sample Explanation 1

以下に塗り分け方の一例を示します。 \# \#\# \# \#\#\# \#\#\#\#\# \#\#\#\#\#\#\#\#\#\#\#\#

Sample Explanation 2

以下の $6$ 通りの塗り分け方が存在します。 \#\# \#\# \#\# \#\# \#\# \#\#\#\# \#\# \#\# \#\# \#\# \#\#

Sample Explanation 3

どのような塗り分け方も条件を満たします。

Sample Explanation 4

塗り分け方の個数を $10^9\ +\ 7$ で割った余りを出力することに注意して下さい。