AT_agc026_d [AGC026D] Histogram Coloring

考虑一个高为 $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 \leq N \leq 100$ - $1 \leq h_i \leq 10^9$ ## 样例解释 1 以下是其中一种涂色方案。 ``` ## ## ### ##### ########### ``` ## 样例解释 2 存在如下 $6$ 种涂色方案。 ``` ## ## ## ## ## ## #### ## ## ## ## ## ## ``` ## 样例解释 3 任意涂色方案都满足条件。 ## 样例解释 4 请注意输出方案数对 $10^9+7$ 取模的结果。 由 ChatGPT 4.1 翻译