题目描述

考虑一个高为 $10^9$、宽为 $N$ 的网格。我们用 $(i, j)$ 表示从左起第 $i$ 列、从下起第 $j$ 行的格子（$1 \leq i \leq N$，$1 \leq j \leq 10^9$）。

すぬけ君对每个 $i = 1, 2, \ldots, 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)$ 这四个格子中，恰好有 $2$ 个是红色，$2$ 个是蓝色。

输入格式

输入以如下格式从标准输入读入。

$N$ $h_1$ $h_2$ $\ldots$ $h_N$

输出格式

输出涂色方案数对 $10^9+7$ 取模的结果。

输入输出样例 #1

输入 #1

9
2 3 5 4 1 2 4 2 1

输出 #1

12800

输入输出样例 #2

输入 #2

2
2 2

输出 #2

6

输入输出样例 #3

输入 #3

5
2 1 2 1 2

输出 #3

256

输入输出样例 #4

输入 #4

9
27 18 28 18 28 45 90 45 23

输出 #4

844733013

说明/提示

限制条件

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

样例解释 1

以下是其中一种涂色方案。

##
##
###
#####
###########

样例解释 2

存在如下 $6$ 种涂色方案。

##
##
##
##
##
##
####
##
##
##
##
##
##

样例解释 3

任意涂色方案都满足条件。

样例解释 4

请注意输出方案数对 $10^9+7$ 取模的结果。