[R27F]公约数 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的数组 $A_1, A_2, \ldots, A_n$。 请计算出有多少个长度为 $n$ 的数组 $X_1, X_2, \ldots, X_n$ 满足以下所有条件：

• $1 \leq X_i \leq A_i$ （对于所有 $1 \leq i \leq n$）
• $\gcd(X_1, X_2, \ldots, X_n) = 1$

由于答案可能很大，请将结果对 $998244353$ 取模。

格式

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $A_1, A_2, \ldots, A_n$。

输出格式

输出一个整数，表示满足条件的序列 $X$ 的数量，对 $998244353$ 取模。

样例

样例输入 #1

3
2 4 4

样例输出 #1

28

数据规模

对于 $30\%$ 的数据，$1 \leq A_i \leq 2000$。

对于 $100\%$ 的数据，$1 \le n \le 100$，$1 \le A_i \le 10^7$。