农夫 Fred 想要重新设计他房子的栅栏。Fred 的栅栏由 $n$ 块高度各异的垂直木板组成。第 $i$ 块木板的高度为 $h_i$ ($1 \le h_i \le n$)。最初，所有高度互不相同。

为了重新设计栅栏，Fred 会选择一段连续的木板区间 $[l \dots r]$ 并对其进行“平整”处理，即通过切割使该区间内所有木板的高度都等于该区间内的最小高度。更具体地说，该区间内所有 $l \le i \le r$ 的木板，其新高度变为 $h'_i = \min\{h_l, h_{l+1}, \dots, h_r\}$。

通过执行若干次（可能为 0 次）此操作，Fred 可以获得多少种不同的栅栏设计？由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

如果两种设计 $A$ 和 $B$ 中存在某块木板的高度不同，则认为它们是不同的设计。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3000$)，表示 Fred 栅栏中木板的数量。

第二行包含 $n$ 个互不相同的整数 $h_i$ ($1 \le h_i \le n, 1 \le i \le n$)，表示每块木板的高度。

输出格式

输出一个整数，表示可以获得的不同栅栏设计的数量，对 $10^9 + 7$ 取模。

样例

样例输入 1

3
1 3 2

样例输出 1

4

样例输入 2

5
1 2 3 4 5

样例输出 2

42

样例输入 3

7
1 4 2 5 3 6 7

样例输出 3

124