Fred el granjero quiere rediseñar la cerca de su casa. La cerca de Fred está compuesta por $n$ tablones de madera verticales de varias alturas. La altura del $i$-ésimo tablón es $h_i$ ($1 \le h_i \le n$). Inicialmente, todas las alturas son distintas.

Para rediseñar la cerca, Fred elegirá algún segmento contiguo $[l \dots r]$ de tablones y los "nivelará", cortándolos para hacer que todas las alturas sean iguales a la altura mínima en ese segmento. Más específicamente, las nuevas alturas del segmento se convierten en $h'_i = \min\{h_l, h_{l+1}, \dots, h_r\}$ para todo $l \le i \le r$.

¿Cuántos diseños diferentes puede obtener Fred aplicando este procedimiento varias veces (posiblemente 0)? Dado que la respuesta puede ser enorme, se requiere que la entregues módulo $10^9 + 7$.

Dos diseños $A$ y $B$ son diferentes si existe algún tablón que tenga una altura distinta en $A$ que en $B$.

Entrada

La primera línea de la entrada contiene $n$ ($1 \le n \le 3\,000$), el número de tablones de la cerca de Fred.

La segunda línea contiene $n$ enteros distintos $h_i$ ($1 \le h_i \le n$, $1 \le i \le n$), las alturas de cada uno de los tablones.

Salida

Imprime un solo entero, el número de diseños de cerca diferentes que se pueden obtener, módulo $10^9 + 7$.

Ejemplos

Entrada 1

3
1 3 2

Salida 1

4

Entrada 2

5
1 2 3 4 5

Salida 2

42

Entrada 3

7
1 4 2 5 3 6 7

Salida 3

124