33129번 - GCDDCG 다국어

문제

You are playing the Greatest Common Divisor Deck-Building Card Game (GCDDCG). There are $N$ cards (numbered from 1ドル$ to $N$). Card $i$ has the value of $A_i,ドル which is an integer between 1ドル$ and $N$ (inclusive).

The game consists of $N$ rounds (numbered from 1ドル$ to $N$). Within each round, you need to build two non-empty decks, deck 1ドル$ and deck 2ドル$. A card cannot be inside both decks, and it is allowed to not use all $N$ cards. In round $i,ドル the greatest common divisor (GCD) of the card values in each deck must equal $i$.

Your creativity point during round $i$ is the product of $i$ and the number of ways to build two valid decks. Two ways are considered different if one of the decks contains different cards.

Find the sum of creativity points across all $N$ rounds. Since the sum can be very large, calculate the sum modulo 998ドル,円 244,円 353$.

입력

The first line consists of an integer $N$ (2ドル ≤ N ≤ 200,円 000$).

The second line consists of $N$ integers $A_i$ (1ドル ≤ A_i ≤ N$).

출력

Output a single integer representing the sum of creativity points across all $N$ rounds modulo 998ドル,円 244,円 353$.

제한

힌트