题目描述

考虑一个拥有 $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), (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

以下是其中一种涂色方式的示例：

  #```