得分 : $1100$ 分

问题陈述

考虑一个有 $10^9$ 行和 $N$ 列的方格。设 $(i, j)$ 为从左起第 $i$ 列 $(1 \leq i \leq N)$ 和从底部起第 $j$ 行 $(1 \leq j \leq 10^9)$ 的方格。

Snuke 已经切掉了网格的一部分，使得对于每个 $i = 1, 2, ..., N$，在第 $i$ 列中剩下的最底部 $h_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$ 取模。

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

记得对结果取模 $10^9 + 7$。