[AGC026D] Histogram Coloring

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

[problemUrl]: https://atcoder.jp/contests/agc026/tasks/agc026_d 高さ $ 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 $ で割った余りを出力せよ。

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 $ で割った余りを出力することに注意して下さい。