分数: 1000 点
问题陈述
有 N 在建建筑物排成一排,编号 1, 2, \ldots, N 从左到右。
给定的是一个整数序列 X 长度 N.建筑物的高度 i, H_i,可以是之间的整数之一 1 和 X_i (含)。
对于每个 i 这样 1 \leq i \leq N,让我们定义 P_i 如下:
- 如果有一个整数 j (1 \leq j < i) 这样 H_j > H_i, P_i 是这样的最大值 j。否则, P_i is -1.
考虑建筑物高度的所有可能组合,找到满足以下条件的整数序列的数量: P 可以是,模 1000000007.
约束
- 1 \leq N \leq 100
- 1 \leq X_i \leq 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N X_1 X_2 \cdots X_N
输出
打印整数序列的数量 P 可以是当考虑建筑物高度的所有可能组合时,模数 1000000007.
示例输入 1
3 3 2 1
示例输出 1
4
我们有六名候选人 H,如下:
- H = (1, 1, 1),其中 P is (-1, -1, -1);
- H = (1, 2, 1),其中 P is (-1, -1, 2);
- H = (2, 1, 1),其中 P is (-1, 1, 1);
- H = (2, 2, 1),其中 P is (-1, -1, 2);
- H = (3, 1, 1),其中 P is (-1, 1, 1);
- H = (3, 2, 1),其中 P is (-1, 1, 2).
因此,有四个整数序列 P 可以是: (-1, -1, -1), (-1, -1, 2), (-1, 1, 1),和 (-1, 1, 2).
示例输入 2
3 1 1 2
示例输出 2
1
我们有两名候选人 H,如下:
- H = (1, 1, 1),其中 P is (-1, -1, -1);
- H = (1, 1, 2),其中 P is (-1, -1, -1).
因此,有一个整数序列 P 可以。
示例输入 3
5 2 2 2 2 2
示例输出 3
16
示例输入 4
13 3 1 4 1 5 9 2 6 5 3 5 8 9
示例输出 4
31155