题目描述

沿着AtCoder大道上有 $N$ 个建筑。一开始，从左边开始数，第 $i$ 座建筑有 $A_i$ 层。

ARC拆迁公司的总经理高桥可以进行以下操作任意次数（也可以不操作）：

• 选择一个他喜欢的正整数 $X$，并朝它的高度开炮，这会导致每栋楼屋高度大于等于 $X$ 的楼层数减少1层。

计算可能的最终建筑景观的数量，结果对 ($10^9 + 7$) 取模。

当满足以下条件时，我们认为两种建筑景观 $A$ 和 $B$ 不同：

• 设景观 $A$ 中从左边开始数的第 $i$ 座建筑的楼层数为 $P_i$；
• 设景观 $B$ 中从左边开始数的第 $i$ 座建筑的楼层数为 $Q_i$；
• 当存在一个或多个索引 $i$，使得 $P_i \neq Q_i$ 时，我们认为景观 $A$ 和 $B$ 不同。

约束条件

• $1 \leq N \leq 100000$
• $1 \leq A_i \leq 10^9$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出

打印答案。

示例输入1

2
1 2

示例输出1

4

有四种可能的建筑高度组合，分别是：

• (建筑1, 建筑2) = $(0, 0)$
• (建筑1, 建筑2) = $(0, 1)$
• (建筑1, 建筑2) = $(1, 1)$
• (建筑1, 建筑2) = $(1, 2)$

示例输入2

6
5 3 4 1 5 2

示例输出2

32

示例输入3

7
314 159 265 358 979 323 846

示例输出3

492018656

共有 $20192492160000$ 种可能的最终建筑景观。正确的输出应该对 $10^9 + 7$ 取模得到 $492018656$。