给你一个整数 $n$ 和一个整数序列 $a_1, a_2, \dots, a_n$。你的任务是求出满足以下条件的整数序列 $(b_1, b_2, \dots, b_n)$ 的数量：

• $1 \le b_i \le a_i$ 对每个 $i$ ($1 \le i \le n$) 均成立。
• $b_i$ 是 $b_{i+1}$ 的因数对每个 $i$ ($1 \le i \le n - 1$) 均成立。

如果两个序列在至少一个位置上不同，则认为它们是不同的。

由于满足条件的序列数量可能很大，请输出答案对 $998\,244\,353$ 取模后的结果。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, 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