問題文

高さ $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$ 個ずつ赤色と青色のマスが存在する。

制約

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

入力

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

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

出力

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

入力例 1

9
2 3 5 4 1 2 4 2 1

出力例 1

12800

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

  #```