题目描述

Fred 有一个长度为 $n$ 的排列 $h$，每次操作他可以选择一段区间 $[l,r]$，令 $h_i = \min_{j=l}^{r}h_j\ (i \in [l,r])$。

问进行若干次操作（可以为 $0$ 次）后不同的数组数量，对 $10^9 + 7$ 取模。

输入格式

第一行一个整数 $n\ (1 \leq n \leq 3000)$。

接下来一行 $n$ 个整数 $h_i\ (1 \leq h_i \leq n)$。

输出格式

输出操作后不同数组的数量模 $10^9+7$ 的值。

3
1 3 2

4

5
1 2 3 4 5

42

7
1 4 2 5 3 6 7

124