

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
一列に並んだ N 棟のビルが建設中であり、ビルには左から順番に 1, 2, \ldots, N の番号がついています。
長さ N の整数列 X が与えられ、ビル i の高さ H_i は、1 以上 X_i 以下の整数のいずれかにすることができます。
1 \leq i \leq N に対して、P_i を次のように定めます。
- H_j > H_i を満たすような整数 j (1 \leq j < i) が存在する場合はそのような j の最大値、存在しない場合は -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 としては、次の 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
3 1 1 2
出力例 2
1
H としては、次の 2 通りが考えられます。
- H = (1, 1, 1) のとき、P は (-1, -1, -1) である
- H = (1, 1, 2) のとき、P は (-1, -1, -1) である
よって、P としてありうる整数列は 1 個です。
入力例 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
Score : 1000 points
Problem Statement
There are N buildings under construction arranged in a row, numbered 1, 2, \ldots, N from left to right.
Given is an integer sequence X of length N. The height of Building i, H_i, can be one of the integers between 1 and X_i (inclusive).
For each i such that 1 \leq i \leq N, let us define P_i as follows:
- If there is an integer j (1 \leq j < i) such that H_j > H_i, P_i is the maximum such j. Otherwise, P_i is -1.
Considering all possible combinations of the buildings' heights, find the number of integer sequences that P can be, modulo 1000000007.
Constraints
- 1 \leq N \leq 100
- 1 \leq X_i \leq 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X_1 X_2 \cdots X_N
Output
Print the number of integer sequences that P can be when all possible combinations of the buildings' heights are considered, modulo 1000000007.
Sample Input 1
3 3 2 1
Sample Output 1
4
We have six candidates for H, as follows:
- H = (1, 1, 1), for which P is (-1, -1, -1);
- H = (1, 2, 1), for which P is (-1, -1, 2);
- H = (2, 1, 1), for which P is (-1, 1, 1);
- H = (2, 2, 1), for which P is (-1, -1, 2);
- H = (3, 1, 1), for which P is (-1, 1, 1);
- H = (3, 2, 1), for which P is (-1, 1, 2).
Thus, there are four integer sequences that P can be: (-1, -1, -1), (-1, -1, 2), (-1, 1, 1), and (-1, 1, 2).
Sample Input 2
3 1 1 2
Sample Output 2
1
We have two candidates for H, as follows:
- H = (1, 1, 1), for which P is (-1, -1, -1);
- H = (1, 1, 2), for which P is (-1, -1, -1).
Thus, there is one integer sequence that P can be.
Sample Input 3
5 2 2 2 2 2
Sample Output 3
16
Sample Input 4
13 3 1 4 1 5 9 2 6 5 3 5 8 9
Sample Output 4
31155