题目描述

有 $N$ 栋正在建设中的大楼排成一列，大楼从左到右依次编号为 $1, 2, \ldots, N$。

给定一个长度为 $N$ 的整数序列 $X$，第 $i$ 栋大楼的高度 $H_i$ 可以是 $1$ 到 $X_i$ 之间的任意整数。

对于 $1 \leq i \leq N$，定义 $P_i$ 如下：

• 如果存在整数 $j\ (1 \leq j < i)$ 满足 $H_j > H_i$，则 $P_i$ 为所有满足条件的 $j$ 中的最大值；如果不存在这样的 $j$，则 $P_i = -1$。

请计算所有可能的大楼高度组合中，$P$ 可能出现的不同整数序列的个数，并对 $1000000007$ 取模后输出。

输入格式

输入通过标准输入给出，格式如下：

$N$ $X_1$ $X_2$ $\cdots$ $X_N$

输出格式

请输出所有可能的大楼高度组合中，$P$ 可能出现的不同整数序列的个数，对 $1000000007$ 取模。

样例 1

输入

3
3 2 1

输出

4

样例 2

输入

3
1 1 2

输出

1

样例 3

输入

5
2 2 2 2 2

输出

16

样例 4

输入

13
3 1 4 1 5 9 2 6 5 3 5 8 9

输出

31155

说明/提示

限制条件

• $1 \leq N \leq 100$
• $1 \leq X_i \leq 10^5$
• 输入均为整数

样例解释 1

$H$ 可能的情况如下，共有 $6$ 种：

• 当 $H = (1, 1, 1)$ 时，$P = (-1, -1, -1)$
• 当 $H = (1, 2, 1)$ 时，$P = (-1, -1, 2)$
• 当 $H = (2, 1, 1)$ 时，$P = (-1, 1, 1)$
• 当 $H = (2, 2, 1)$ 时，$P = (-1, -1, 2)$
• 当 $H = (3, 1, 1)$ 时，$P = (-1, 1, 1)$
• 当 $H = (3, 2, 1)$ 时，$P = (-1, 1, 2)$

因此，$P$ 可能出现的不同整数序列有 $(-1, -1, -1),\ (-1, -1, 2),\ (-1, 1, 1),\ (-1, 1, 2)$ 共 $4$ 个。

样例解释 2

$H$ 可能的情况如下，共有 $2$ 种：

• 当 $H = (1, 1, 1)$ 时，$P = (-1, -1, -1)$
• 当 $H = (1, 1, 2)$ 时，$P = (-1, -1, -1)$

因此，$P$ 可能出现的不同整数序列只有 $1$ 个。

由 ChatGPT 4.1 翻译