시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB444100.000%

문제

Bajtazar jest niezwykle dumny ze swojej kolekcji rzadkich monet. Zbierał je przez wiele lat, dbając o to, by żadne dwie nie były do siebie podobne. Obecnie ma $n$ monet ponumerowanych tak, że $i$-ta moneta ma rozmiar dokładnie $i$.

Jako że kolekcja Bajtazara ostatnio się powiększyła, był on zmuszony kupić nowy klaser. Jest w nim dokładnie $n$ przegród na monety, każda o określonym rozmiarze. Oczywiście żadnej monety nie można włożyć do zbyt małej przegrody. Nic nie stoi jednak na przeszkodzie, by włożyć ją do przegrody większej.

Bajtazar zastanawia się teraz do których przegród włożyć poszczególne monety. Po sprawdzeniu wielu kombinacji zaintrygowało go również pytanie, na ile sposobów może zapełnić klaser. Ponieważ liczba ta może być bardzo duża, Bajtazarowi wystarczy jej reszta z dzielenia przez $10^9+7$. Napisz program, który zaspokoi jego ciekawość.

입력

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą: $n$ ($1 ≤ n ≤ 1\,000\,000$). W następnym wierszu znajduje się $n$ liczb całkowitych $a_i$ ($1 ≤ a_i ≤ n$) pooddzielanych pojedynczymi odstępami. Liczba $a_i$ mówi, jaką największą monetę można włożyć do $i$-tej przegrody.

출력

Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą - resztę z dzielenia liczby sposobów zapełnienia klasera przez $10^9+7$.

예제 입력 1

4
4 2 4 2

예제 출력 1

4