Fred le fermier souhaite redessiner la clôture de sa maison. La clôture de Fred est composée de $n$ planches de bois verticales de hauteurs variées. La hauteur de la $i$-ième planche est $h_i$ ($1 \le h_i \le n$). Initialement, toutes les hauteurs sont distinctes.

Afin de redessiner la clôture, Fred choisit un segment contigu $[l \dots r]$ de planches et les « nivelle » en les coupant de manière à ce que toutes les hauteurs soient égales à la hauteur minimale de ce segment. Plus précisément, les nouvelles hauteurs du segment deviennent $h'_i = \min\{h_l, h_{l+1}, \dots, h_r\}$ pour tout $l \le i \le r$.

Combien de designs différents Fred peut-il obtenir en appliquant cette procédure plusieurs fois (éventuellement zéro) ? Comme la réponse peut être très grande, vous devez l'afficher modulo $10^9 + 7$.

Deux designs $A$ et $B$ sont différents s'il existe au moins une planche qui a une hauteur différente dans $A$ que dans $B$.

Entrée

La première ligne de l'entrée contient $n$ ($1 \le n \le 3\,000$), le nombre de planches de la clôture de Fred.

La deuxième ligne contient $n$ entiers distincts $h_i$ ($1 \le h_i \le n$, $1 \le i \le n$), les hauteurs de chacune des planches.

Sortie

Affichez un seul entier, le nombre de designs de clôture différents pouvant être obtenus, modulo $10^9 + 7$.

Exemples

Entrée 1

3
1 3 2

Sortie 1

4

Entrée 2

5
1 2 3 4 5

Sortie 2

42

Entrée 3

7
1 4 2 5 3 6 7

Sortie 3

124