P14009 Number Game

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$.

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

Output a single line containing the answer.

### Data Range **This problem uses bundled tests.** | Subtask ID | $n\le$ | $a_i\le$ | Score | | :--------: | :----: | :------: | :---: | | 1 | 5 | 5 | 10 | | 2 | 200 | 100 | 30 | | 3 | 2000 | 1000 | 30 | | 4 | $7\times 10^4$ | $7\times 10^4$ | 30 | Translated by ChatGPT 4.1