/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 1100 点
問題文
高さ 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
以下に塗り分け方の一例を示します。
# ## # ### # #### ### #########
入力例 2
2 2 2
出力例 2
6
以下の 6 通りの塗り分け方が存在します。
## ## ## ## ## ## ## ## ## ## ## ##
入力例 3
5 2 1 2 1 2
出力例 3
256
どのような塗り分け方も条件を満たします。
入力例 4
9 27 18 28 18 28 45 90 45 23
出力例 4
844733013
塗り分け方の個数を 10^9 + 7 で割った余りを出力することに注意して下さい。
Score : 1100 points
Problem Statement
Let us consider a grid of squares with 10^9 rows and N columns. Let (i, j) be the square at the i-th column (1 \leq i \leq N) from the left and j-th row (1 \leq j \leq 10^9) from the bottom.
Snuke has cut out some part of the grid so that, for each i = 1, 2, ..., N, the bottom-most h_i squares are remaining in the i-th column from the left. Now, he will paint the remaining squares in red and blue. Find the number of the ways to paint the squares so that the following condition is satisfied:
- Every remaining square is painted either red or blue.
- For all 1 \leq i \leq N-1 and 1 \leq j \leq min(h_i, h_{i+1})-1, there are exactly two squares painted red and two squares painted blue among the following four squares: (i, j), (i, j+1), (i+1, j) and (i+1, j+1).
Since the number of ways can be extremely large, print the count modulo 10^9+7.
Constraints
- 1 \leq N \leq 100
- 1 \leq h_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N h_1 h_2 ... h_N
Output
Print the number of the ways to paint the squares, modulo 10^9+7.
Sample Input 1
9 2 3 5 4 1 2 4 2 1
Sample Output 1
12800
One of the ways to paint the squares is shown below:
# ## # ### # #### ### #########
Sample Input 2
2 2 2
Sample Output 2
6
There are six ways to paint the squares, as follows:
## ## ## ## ## ## ## ## ## ## ## ##
Sample Input 3
5 2 1 2 1 2
Sample Output 3
256
Every way to paint the squares satisfies the condition.
Sample Input 4
9 27 18 28 18 28 45 90 45 23
Sample Output 4
844733013
Remember to print the number of ways modulo 10^9 + 7.