농부 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$는 어떤 판자의 높이가 $A$와 $B$에서 서로 다를 경우 다른 디자인으로 간주합니다.

입력

첫 번째 줄에는 Fred의 울타리에 있는 판자의 개수 $n$ ($1 \le n \le 3000$)이 주어집니다.

두 번째 줄에는 각 판자의 높이를 나타내는 $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