Problem description

Janek od zawsze lubił liczby, a w szczególności permutacje. Ostatnio zainteresowały go ciekawe własności pewnych ciągów. Dostał do analizy permutację P długości n, czyli ciąg, w którym każda liczba od 1 do n występuje dokładnie raz.

Janek chciałby policzyć, ile istnieje niepustych podciągów (niekoniecznie spójnych) tej permutacji (czyli takich ciągów, które powstają przez usunięcie dowolnych elementów, ale bez zmiany kolejności), które spełniają następujący warunek:

Dla każdego kolejnego elementu podciągu x₁, x₂, …, x_k (gdzie k ≥ 1), zachodzi: - (x_i + 1 mod  x_i = 1) dla 1 ≤ i < k

Janek szybko zauważył, że takich podciągów może być bardzo dużo, dlatego chciałby poznać tylko ich liczbę modulo 10⁹ + 7.

Twoim zadaniem jest pomóc mu w obliczeniu odpowiedzi.

Wejście

W pierwszym wierszu znajduje się jedna liczba całkowita n — długość permutacji.
W drugim wierszu znajduje się n liczb całkowitych P₁, P₂, …, P_n — permutacja liczb od 1 do n.

Wyjście

Wypisz jedną liczbę — liczbę podciągów spełniających warunek (x_i + 1 mod  x_i = 1), modulo 10⁹ + 7.

Ograniczenia

• 1 ≤ n ≤ 10⁶
• P jest permutacją liczb od 1 do n

Przykład

5
3 2 1 4 5

11