Description

Given a positive integer $n$ and a sequence of positive integers $a$, where $n$ represents the length of the sequence $a$.

We define the weight of an interval $[l, r]$ as $f(l, r)$, where:

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

Find the sum of the weights of all intervals, that is, compute:

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

Output the answer modulo $998244353$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers representing the sequence $a$.

Output Format

Output a single line containing the answer.

2
1 2

4

5
2 4 4 5 4 

1301

10
1 7 5 5 7 6 9 2 4 8 

10816520

Hint

Data Range

This problem uses bundled tests.

Subtask ID	$n\le$	$a_i\le$	Score
1	5		10
2	200	100	30
3	2000	1000
4	$7\times 10^4$

Translated by ChatGPT 4.1