Problem Description

Fred has a permutation \( h \) of length \( n \). In each operation, he can choose an interval \([l, r]\) and set \( h_i = \min_{j=l}^{r} h_j \) for all \( i \in [l, r] \).

Determine the number of distinct arrays that can be obtained after performing several operations (which can be zero) modulo \( 10^9 + 7 \).

Input Format

The first line contains an integer \( n \) \((1 \leq n \leq 3000)\).

The next line contains \( n \) integers \( h_i \) \((1 \leq h_i \leq n)\).

Output Format

Output the number of distinct arrays after operations modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

3
1 3 2

Sample Output #1

4

Sample Input #2

5
1 2 3 4 5

Sample Output #2

42

Sample Input #3

7
1 4 2 5 3 6 7

Sample Output #3

124

见题面 Input 部分

见题面 Output 部分