Rearranged Flower Fields

DLS has \(N\) flower fields, where the \(i\)-th field contains \(a_i\) flowers. He loves unusual flower fields, so he decides to rearrange the fields arbitrarily and then pick flowers from left to right. However, he has a strange habit: when arriving at a field with \(a_i\) flowers, if there exists any field to its left whose number of flowers is a divisor of \(a_i\), he will not pick the flowers from that field.

For a given ordering (permutation) of the fields, define the total number of flowers picked as the sum of the \(a_i\) for each field that is picked. DLS is curious to know, over all possible rearrangements of the fields, what is the sum of picked flowers. Since the answer can be very large, output it modulo \(998244353\).

Note: A number \(x\) is said to be a divisor of \(y\) if there exists an integer \(k\) such that \(y=k\cdot x\). In particular, every number divides itself. Therefore, if two fields have the same number of flowers, only the one that appears first in the order will have its flowers picked.

Hint: By linearity of expectation, one may compute, for each field with value \(x\), the probability that no other field with a flower count that divides \(x\) appears before it. In an arbitrary permutation, among the set \(S\) containing the field itself and all other fields whose flower counts divide \(x\), the field is picked if and only if it is the first to appear. Hence, its probability of being picked is \(1/|S|\). If we let \(f(x)\) be the frequency of a field with exactly \(x\) flowers, then for a field with \(x\) flowers the size of \(S\) is \(\sum_{d|x} f(d)\). The final answer is \(N!\) multiplied by the sum of contributions \(\frac{x}{\sum_{d|x} f(d)}\) over all fields, modulo \(998244353\).

inputFormat

The first line contains a single integer \(N\) (the number of flower fields).

The second line contains \(N\) space-separated integers \(a_1, a_2, \ldots, a_N\) where \(a_i\) is the number of flowers in the \(i\)-th field.

\(1 \leq N \leq 10^5\) and \(1 \leq a_i \leq M\) (with \(M\) being a moderate integer, for example \(10^6\)).

outputFormat

Output a single integer: the sum of picked flowers over all possible rearrangements, modulo \(998244353\).

sample

2
3 4

14