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.

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.

Constraints

• $1 \leq N \leq 100$
• $1 \leq X_i \leq 10^5$
• All values in input are integers.

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

见题面 Input 部分

见题面 Output 部分