分数: 1100 点
问题陈述
让我们考虑一个正方形网格 10^9 行和 N 列。让 (i, j) 是位于 i第列 (1 \leq i \leq N) 从左侧开始, j第行 (1 \leq j \leq 10^9) 从底部开始。
Snuke 切掉了网格的某些部分,这样,对于每个 i = 1, 2, ..., N,最底部 h_i 方块仍保留在 i左起第 列。 现在,他将把剩下的方块涂成红色和蓝色。 求出绘制正方形的方法的数量,以满足以下条件:
- 每个剩余的方块都被涂成红色或蓝色。
- 对于所有人 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).
由于路数可能非常大,因此打印计数模数 10^9+7.
约束
- 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
绘制正方形有六种方法,如下:
## ## ## ## ## ## ## ## ## ## ## ##
示例输入 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.