题目描述

小 I 今天学习了快速最小公倍数变换（Fast Least-Common-Multiple Transform, FLT），于是他想考考你。

给定一个长度为 $n$ 的正整数序列 $r_1,r_2,\cdots,r_n$。你需要做以下操作恰好一次：

• 选择整数 $i,j$ 使得 $1 \le i < j \le n$。在序列末尾加入 $(r_i+r_j)$，并将 $r_i$ 和 $r_j$ 从序列中删除。

可以注意到总共有 $\frac{n(n-1)}{2}$ 种可能的操作，每种操作会得到一个长度为 $n-1$ 的序列。

你需要对所有的这 $\frac{n(n-1)}{2}$ 个序列，求出序列中所有元素的最小公倍数，并给出它们的和模 $998244353$ 的值。

输入格式

输入的第一行包含一个正整数 $n$，表示序列的长度。接下来一行 $n$ 个正整数 $r_1,r_2,\cdots,r_n$，描述初始序列。

输出格式

输出一行一个整数，表示所有序列的最小公倍数的和模 $998244353$ 的值。

3
2 3 4

40

数据范围与提示

对于所有测试数据，$2 \le n \le 5 \times 10^5, 1 \le r_1,r_2,\cdots,r_n \le 10^6$。