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\ (i \in [l,r])$.

After performing several operations (possibly $0$ operations), find the number of distinct arrays that can be obtained, 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 the operations modulo $10^9 + 7$.

3
1 3 2

4

5
1 2 3 4 5

42

7
1 4 2 5 3 6 7

124

Hint

Translated by ChatGPT 5