You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

任何数和 $0$ 的最大公约数是它本身。

题目描述

小 X 正在研究一个长度为 $n$ 的数列 $\{A\}$，他通过查阅资料，偶然间发现了一个叫做“七连击”的式子：$\sum\limits_{a=1}^n\sum\limits_{b=a+1}^n\sum\limits_{c=b+1}^n\sum\limits_{d=c+1}^n\sum\limits_{e=d+1}^n\sum\limits_{f=e+1}^n\sum\limits_{g=f+1}^n ((\gcd\limits_{i=1}^aA_i)+(\gcd\limits_{i=a+1}^bA_i)+(\gcd\limits_{i=b+1}^cA_i)+(\gcd\limits_{i=c+1}^dA_i)+(\gcd\limits_{i=d+1}^eA_i)+(\gcd\limits_{i=e+1}^fA_i)+(\gcd\limits_{i=f+1}^gA_i))$。

其中 $(\gcd\limits_{i=l}^r A_i)$ 表示 $A_l,A_{l+1},\dots,A_r$ 的最大公约数。

现在小 X 希望你求出这个式子的值。 由于答案可能很大，他只需要你输出答案对 $998244353$ 取模的结果。

输入格式

第一行一个整数 $n$，表示序列长度。

第二行 $n$ 个整数表示序列 $\{A\}$。

输出格式

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

7
3 4 2 5 6 3 4

27

10
9 9 9 8 8 8 72 72 72 2

20040

20
3 5 5 5 7 15 20 14 28 9 36 3 4 5 7 19 16 28 37 29

3207876

30
1 9 8 8 8 3 3 4 2 2 3 3 9 8 8 6 6 7 3 3 6 6 8 8 4 3 3 6 6 8

34595704

50
9 9 9 9 63 72 36 36 4 4 4 20 20 20 10 10 70 2 12 9 9 9 9 63 72 36 36 4 4 4 20 20 20 10 10 70 2 12 9 9 9 9 63 72 36 36 4 4 4 4

24688627

提示

本题采用捆绑测试。

对于所有数据，$7\le n\le 10^5$，$0\le A_i\le 10^9$。

子任务编号	$n\leq$	$A_i\leq$	特殊性质	分数
$0$	$7$	$10^9$	否	$1$
$1$	$10$			$9$
$2$	$100$			$10$
$3$	$1000$			$20$
$4$	$10^5$	$100$		$10$
$5$		$10^9$	是
$6$			否	$40$

特殊性质： 对于任意满足 $1\le i\le n$ 的整数 $i$，$A_i$ 在 $[0,10^9]$ 中随机生成。