AT_arc104_f [ARC104F] Visibility Sequence

有 $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 \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 翻译