Hasar İşləri#10885
Fred Fermer həyətinin ətrafındakı hasarı yenidən dizayn etmək istəyir. Hasar müxtəlif hündürlükdə olan şaquli taxta parçalarından ibarətdir. -ci taxtanın hündürlüyü h_i~(1 \le h_i \le n)-dir.
Hasarı yenidən dizayn etmək üçün Fred aşağıdakı əməliyyatı hər hansı bir sayda (mümkün olan dəfə) təkrarlaya bilər:
Taxtaların ardıcıl olan bir segmentini [l, r] seçin və bütün taxtaların həmin segmentdəki minimal hündürlüyə bərabər olan eyni hündürlükdə olacağı şəkildə kəsin.
Formal olaraq, [l, r] segmentinə əməliyyatı tətbiq etdikdən sonra bu segmentdəki taxtaların hündürlükləri aşağıdakı kimi olur:
Fred bu əməliyyatı bir neçə dəfə tətbiq etməklə neçə müxtəlif hasar dizaynı əldə edə bilər? Cavab böyük ola biləcəyi üçün, 10^9 + 7 modulu ilə nəticəni çap edin.
İki hasar dizaynı və fərqlidir, əgər və arasında ən azı bir taxtanın hündürlüyü fərqlidirsə.
Birinci sətir n~(1 \le n \le 3000), hasarda olan taxtaların sayını göstərən tam ədədini ehtiva edir.
İkinci sətir taxtaların başlanğıc hündürlüklərini göstərən müxtəlif tam ədədlər h_i~(1 \le h_i \le n, 1 \le i \le n) ehtiva edir.
Modul 10^9 + 7 ilə əldə edilə bilən müxtəlif hasar dizaynlarının sayını çap edin.
Nümunə 1
Nümunə 2
Nümunə 3