Problem description

Jasio, czekając na Twoją pomoc z obliczaniem dobrych LISów (longest increasing subsequence), postanowił pomyśleć nad czymś łatwiejszym. Tym razem padło na MISy (maximal increasing subsequence).

Jak zapewne wiesz, podciągiem ciągu A nazywamy dowolny ciąg, który można uzyskać, usuwając niektóre (być może żadnego lub nawet wszystkie) elementy A i odczytując pozostawione elementy od lewej do prawej. Podciąg rosnący to podciąg, w którym każdy kolejny element jest większy od poprzedniego. Podciąg rosnący jest maksymalny (jest MISem), gdy przywrócenie (“od-usunięcie”) dowolnego elementu z oryginalnego ciągu spowodowałoby, że nie byłby to już podciąg rosnący. Inaczej mówiąc jest to podciąg rosnący, którego nie można już lokalnie powiększyć przywracając do niego żadnego elementu z A.

Zwróć uwagę, że MIS niekoniecznie musi być LISem (najdłuższym podciągiem rosnącym). Przykładowo: dla ciągu (1,5,4,20,10,15) zarówno (1,5,10,15) jak i (1,5,20) są MISami, choć tylko ten pierwszy jest LISem. Są jeszcze dwa inne MISy – jeden z nich jest trzyelementowy, a jeden czteroelementowy.

Jasio chciałby dla ustalonego ciągu A wyznaczyć liczbę różnych jego MISów. Dwa MISy uznajemy za różne, gdy podzbiory wybranych pozycji w ciągach są różne. Ponieważ Jasio podejrzewa, że ta liczba może być duża i jest to typowe zadanie algorytmiczne, w którym nie chcemy, żebyś implementował(a) arytmetykę dużych liczb, Jasiowi wystarczy poznać resztę z dzielenia tego wyniku przez 10⁹ + 7. Czy pomożesz mu w tym zadaniu?

Napisz program, który: wczyta ciąg A, wyznaczy liczbę jego maksymalnych podciągów rosnących i wypisze wynik na standardowe wyjście.

Dla uproszczenia: Możesz założyć, że ciąg wejściowy jest generowany w sposób pseudolosowy: dla każdego testu ustalana jest długość N ciągu i wartość M ≥ N, a potem każdy z N elementów generowanego ciągu jest losowany niezależnie z przedziału [1,M].

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość ciągu A. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych A_i, pooddzielanych pojedynczymi odstępami. Są to kolejne elementy ciągu A.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita – reszta z dzielenia przez 10⁹ + 7 liczby MISów w ciągu podanym na wejściu.

Ograniczenia

1 ≤ N ≤ 200 000, 1 ≤ A_i ≤ 10⁹.

Przykład

6
1 5 4 20 10 15

4