정수 $n$과 정수 수열 $a_1,a_2,\ldots,a_n$이 주어집니다. 다음 조건을 만족하는 정수 수열 $(b_1,b_2,\ldots,b_n)$의 개수를 구하세요:

• 모든 $i$ ($1 \le i \le n$)에 대해 $1 \le b_i \le a_i$입니다.

• 모든 $i$ ($1 \le i \le n-1$)에 대해 $b_i$는 $b_{i+1}$의 약수입니다.

적어도 한 위치에서 값이 다르면 두 수열은 서로 다르다고 봅니다.

이러한 수열의 개수가 클 수 있으므로 답을 $998\,244\,353$으로 나눈 나머지를 구하세요.

입력

입력의 첫 번째 줄에는 정수 $n$ ($1 \le n \le 200\,000$)이 주어집니다.

두 번째 줄에는 $n$개의 정수 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 200\,000$)이 주어집니다.

출력

조건을 만족하는 서로 다른 수열의 개수를 $998\,244\,353$으로 나눈 나머지를 출력하세요.

예제

입력 1

2
2 4

출력 1

6

참고

조건을 만족하는 모든 수열은 $(2,4)$, $(2,2)$, $(1,4)$, $(1,3)$, $(1,2)$, $(1,1)$입니다.

입력 2

6
265 9801 192168 200000 192018 199809

출력 2

16555779