Fast Least Common Multiple Transform

Little I has just learned about the Fast Least-Common-Multiple Transform (FLT) and now challenges you with a problem.

You are given a sequence of n positive integers \(r_1,r_2,\cdots,r_n\). You are required to perform the following operation exactly once:

• Choose two indices \(i,j\) such that \(1 \le i < j \le n\). Remove \(r_i\) and \(r_j\) from the sequence and append \(r_i+r_j\) to the end of the sequence.

It can be observed that there are a total of \(\frac{n(n-1)}{2}\) possible operations, each resulting in a sequence of length \(n-1\). For each of these sequences, compute the least common multiple (LCM) of all its elements. Your task is to find the sum of these LCM values modulo \(998244353\).

Note: All formulas are presented in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(n\) representing the length of the sequence.

The second line contains \(n\) space-separated positive integers \(r_1, r_2, \ldots, r_n\).

outputFormat

Output the sum of the LCM values of all generated sequences, taken modulo \(998244353\).

sample

3
1 2 3

12