Problem Statement

There are $N$ buildings under construction arranged in a row, numbered $1,2,\dots ,N$ from left to right.

Given is an integer sequence $X$ of length $N$. The height of Building $i$, Hi​, can be one of the integers between $1$ and Xi​ (inclusive).

For each $i$ such that $1\le i\le N$, let us define Pi​ as follows:

• If there is an integer $j(1\le j<i)$ such that Hj​>Hi​, Pi​ is the maximum such $j$. Otherwise, Pi​ is $-1$.

Considering all possible combinations of the buildings' heights, find the number of integer sequences that $P$ can be, modulo $1000000007$.

Constraints

• $1\le N\le 100$
• 1≤Xi​≤105
• 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