Personal LCM
We have an integer sequence of length NN: A0,A1,⋯,AN−1A0,A1,⋯,AN−1.
Find the following sum (lcm(a,b)lcm(a,b) denotes the least common multiple of aa and bb):
- ∑N−2i=0∑N−1j=i+1lcm(Ai,Aj)∑i=0N−2∑j=i+1N−1lcm(Ai,Aj)
Since the answer may be enormous, compute it modulo 998244353998244353.
Constraints
- 1≤N≤2 * 1051≤N≤200000
- 1≤Ai≤106
- All values in input are integers.
Input:
First line of input will be consist of a single N, number of elements.
In next line you will get N space seperated Integers. A0 A1 A2 A3 A4......AN-1
Output:
Print the sum modulo 998244353998244353.
Example:
Input:
3
2 4 6
Output:
22
Explaination:
lcm(2,4)+lcm(2,6)+lcm(4,6)=4+6+12=22lcm(2,4)+lcm(2,6)+lcm(4,6)=4+6+12=22.