Farmer Fred chce przebudować płot wokół swojego domu. Płot Freda składa się z $n$ pionowych drewnianych desek o różnych wysokościach. Wysokość $i$-tej deski wynosi $h_i$ ($1 \le h_i \le n$). Początkowo wszystkie wysokości są różne.

Aby przebudować płot, Fred wybiera pewien spójny segment $[l \dots r]$ desek i „wyrównuje” je, przycinając je tak, aby wszystkie miały wysokość równą minimalnej wysokości w tym segmencie. Mówiąc dokładniej, nowe wysokości desek w segmencie stają się równe $h'_i = \min\{h_l, h_{l+1}, \dots, h_r\}$ dla wszystkich $l \le i \le r$.

Ile różnych projektów płotu może uzyskać Fred, stosując tę procedurę kilkukrotnie (być może zero razy)? Ponieważ wynik może być bardzo duży, należy podać go modulo $10^9 + 7$.

Dwa projekty $A$ i $B$ są różne, jeśli istnieje przynajmniej jedna deska, która ma inną wysokość w projekcie $A$ niż w projekcie $B$.

Wejście

Pierwsza linia wejścia zawiera liczbę $n$ ($1 \le n \le 3000$), liczbę desek w płocie Freda.

Druga linia zawiera $n$ różnych liczb całkowitych $h_i$ ($1 \le h_i \le n$, $1 \le i \le n$), oznaczających wysokości poszczególnych desek.

Wyjście

Wypisz pojedynczą liczbę całkowitą, liczbę różnych możliwych projektów płotu, które można uzyskać, modulo $10^9 + 7$.

Przykład

Wejście 1

3
1 3 2

Wyjście 1

4

Wejście 2

5
1 2 3 4 5

Wyjście 2

42

Wejście 3

7
1 4 2 5 3 6 7

Wyjście 3

124