AT_agc026_d [AGC026D] Histogram Coloring

[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/A

N/A

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