题目描述

给出一个正整数 $n$ 以及正整数序列 $a$，其中 $n$ 表示序列 $a$ 的长度。

我们定义一个区间 $[l,r]$ 的权值为 $f(l,r)$，其中：

$$f(l,r)=\sum^{a_l}_{b_1=1}\sum^{a_{l+1}}_{b_2=1}\sum^{a_{l+2}}_{b_3=1}\dots\sum^{a_{r}}_{b_{r-l+1}=1} [\gcd(b_1,b_2,b_3,\dots,b_{r-l+1})=1] $$

求所有区间的权值之和，即求:

$$\sum^{n}_{l=1} \sum^{n}_{r=l} f(l,r)$$

答案对 $998244353$ 取模。

输入格式

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

第二行，$n$ 个数表示的序列 $a$。

输出格式

共 $1$ 行，表示答案。

2
1 2

4

5
2 4 4 5 4 

1301

10
1 7 5 5 7 6 9 2 4 8 

10816520

提示

数据范围

本题使用捆绑测试。

子任务编号	$n\le$	$a_i\le$	得分
$1$	$5$		$10$
$2$	$200$	$100$	$30$
$3$	$2000$	$1000$
$4$	$7\times 10^4$