题目描述

AtCoder 街道上建有 $N$ 栋大楼。最初，从左到右第 $i$ 栋大楼有 $A_i$ 层。

ARC 拆迁公司的社长高桥君可以进行如下操作任意多次，也可以一次都不进行：

• 任选一个正整数 $X$，从第 $X$ 层高度发射大炮。此时，所有当前高度不少于 $X$ 层的大楼，其层数都会减少 $1$。

请计算最终可能出现的不同大楼景观的数量，并将结果对 $10^{9} + 7$ 取模后输出。

这里，若存在某个 $i$，使得景观 A 的第 $i$ 栋大楼高度 $P_i$ 与景观 B 的第 $i$ 栋大楼高度 $Q_i$ 不同，则认为景观 A 和景观 B 是不同的。

输入格式

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

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

输出格式

请输出答案。

样例 1

输入

2
1 2

输出

4

样例 2

输入

6
5 3 4 1 5 2

输出

32

样例 3

输入

7
314 159 265 358 979 323 846

输出

492018656

说明/提示

限制条件

• $1 \leq N \leq 100000$
• $1 \leq A_i \leq 10^{9}$
• 输入均为整数

样例解释 1

操作后可能出现的大楼高度有如下 $4$ 种情况：

• （大楼 $1$ 的层数, 大楼 $2$ 的层数）= $(0, 0)$
• （大楼 $1$ 的层数, 大楼 $2$ 的层数）= $(0, 1)$
• （大楼 $1$ 的层数, 大楼 $2$ 的层数）= $(1, 1)$
• （大楼 $1$ 的层数, 大楼 $2$ 的层数）= $(1, 2)$

样例解释 3

一共可能有 $20192492160000$ 种景观，将其对 $10^{9} + 7$ 取模后，输出 $492018656$ 即为正确答案。

由 ChatGPT 4.1 翻译