计数

小 H 正在整理一批因子标签。

给定长度为 $n$ 的正整数序列 $a_1, a_2, \ldots, a_n$。你需要计算有多少个长度为 $2n$ 的正整数序列 $b_1, b_2, \ldots, b_{2n}$，同时满足以下两个条件：

1. 对于 $1 \le i \le n$，有 $b_i \mid b_{i+n}$ 且 $b_{i+n} \mid a_i$。
2. $\displaystyle\prod_{i=1}^{n} b_{i+n} \le \prod_{i=1}^{n} b_i^2$。

其中 $x \mid y$ 表示 $x$ 整除 $y$。

答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。

输出格式

一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例 1

输入

2
2 3

输出

5

说明

满足条件的序列 $b = (b_1, b_2, b_3, b_4)$ 共 $5$ 个：

• $(1, 1, 1, 1)$：$b_3 \cdot b_4 = 1 \le 1 = b_1^2 \cdot b_2^2$；
• $(1, 3, 1, 3)$：$1 \times 3 = 3 \le 9 = 1 \times 9$；
• $(1, 3, 2, 3)$：$2 \times 3 = 6 \le 9 = 1 \times 9$；
• $(2, 1, 2, 1)$：$2 \times 1 = 2 \le 4 = 4 \times 1$；
• $(2, 3, 2, 3)$：$2 \times 3 = 6 \le 36 = 4 \times 9$。

样例 2

输入

3
4 6 10

输出

249

提示

本题共 $20$ 组数据。

对于所有数据，$1 \le n \le 100$，$1 \le a_i \le 10^9$。