Problem Description

Little I is learning the Fast Least-Common-Multiple Transform (Fast Least-Common-Multiple Transform, FLT), so he wants to test you.

You are given a positive integer sequence $r_1, r_2, \cdots, r_n$ of length $n$. You need to perform the following operation exactly once:

• Choose integers $i, j$ such that $1 \le i < j \le n$. Append $(r_i + r_j)$ to the end of the sequence, and delete $r_i$ and $r_j$ from the sequence.

Note that there are $\frac{n(n-1)}{2}$ possible operations in total, and each operation produces a sequence of length $n-1$.

For all these $\frac{n(n-1)}{2}$ sequences, you need to compute the least common multiple of all elements in the sequence, and output the sum of these values modulo $998244353$.

Input Format

The first line contains a positive integer $n$, representing the length of the sequence. The next line contains $n$ positive integers $r_1, r_2, \cdots, r_n$, describing the initial sequence.

Output Format

Output one integer on one line, representing the sum of the least common multiples of all resulting sequences modulo $998244353$.

3
2 3 4

40

Hint

Sample Explanation 1

• When $i = 1, j = 2$, the resulting sequence is $\{4, 5\}$, and the least common multiple is $20$.
• When $i = 1, j = 3$, the resulting sequence is $\{3, 6\}$, and the least common multiple is $6$.
• When $i = 2, j = 3$, the resulting sequence is $\{2, 7\}$, and the least common multiple is $14$.

Therefore, the output is $20 + 6 + 14 = 40$.

Subtasks

For all testdata, $2 \le n \le 5 \times 10^5$, and $1 \le r_1, r_2, \cdots, r_n \le 10^6$.

Source

From the 2023 Tsinghua University Programming Contest and Intercollegiate Invitational (THUPC2023) Preliminary.

Solutions and other resources are available at https://github.com/THUSAAC/THUPC2023-Pre.

Translated by ChatGPT 5