← 返回题目列表

AtCoder · agc026_d

D. 直方图着色

中文机器翻译题面 查看原题

分数: 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.