Dana jest liczba całkowita $n$ oraz ciąg liczb całkowitych $a_1,a_2,\ldots,a_n$. Twoim zadaniem jest wyznaczenie liczby ciągów liczb całkowitych $(b_1,b_2,\ldots,b_n)$ spełniających następujące warunki:

• $1 \le b_i \le a_i$ dla każdego $i$ ($1 \le i \le n$).

• $b_i$ jest dzielnikiem $b_{i+1}$ dla każdego $i$ ($1 \le i \le n-1$).

Dwa ciągi uznaje się za różne, jeśli różnią się na co najmniej jednej pozycji.

Ponieważ liczba takich ciągów może być duża, oblicz odpowiedź modulo $998\,244\,353$.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 200\,000$).

Drugi wiersz zawiera $n$ liczb całkowitych $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 200\,000$).

Wyjście

Wypisz liczbę różnych ciągów spełniających warunki, modulo $998\,244\,353$.

Przykład

Wejście 1

2
2 4

Wyjście 1

6

Uwagi

Wszystkie ciągi spełniające warunki to: $(2,4)$, $(2,2)$, $(1,4)$, $(1,3)$, $(1,2)$ oraz $(1,1)$.

Wejście 2

6
265 9801 192168 200000 192018 199809

Wyjście 2

16555779