Seven GCD Strikes

In this problem, you are given an array (A) of length (n). You need to compute the value of the following expression modulo (998244353): [ S = \sum_{1 \le a < b < c < d < e < f < g \le n} \Bigl( \gcd(A_1, A_2, \dots, A_a) + \gcd(A_{a+1}, \dots, A_b) + \gcd(A_{b+1}, \dots, A_c) + \gcd(A_{c+1}, \dots, A_d) + \gcd(A_{d+1}, \dots, A_e) + \gcd(A_{e+1}, \dots, A_f) + \gcd(A_{f+1}, \dots, A_g) \Bigr ) ] Here, (\gcd(A_l, A_{l+1}, \dots, A_r)) denotes the greatest common divisor of the numbers (A_l, A_{l+1}, \dots, A_r).

Note: The seven indices (a,b,c,d,e,f,g) satisfy (1 \le a < b < c < d < e < f < g \le n), which partitions the array into 7 non-empty contiguous segments. Your task is to compute (S \bmod 998244353).

inputFormat

The first line contains a single integer (n) (the length of the array). The second line contains (n) space-separated integers, representing the array (A).

outputFormat

Output a single integer denoting the value of the given expression modulo (998244353).

sample

7
1 1 1 1 1 1 1

7