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\).
Output
Output a single integer representing the sum of creativity points across all \(N\) rounds modulo \(998\,244\,353\).
Note
Explanation for the sample input/output #1
The creativity point during each of rounds \(1\) and \(2\) is \(0\).
During round \(3\), there are \(12\) ways to build both decks. Denote \(B\) and \(C\) as the set of card numbers within deck \(1\) and deck \(2\), respectively. The \(12\) ways to build both decks are:
- \(B = \{ 1 \}, C = \{ 2 \}\);
- \(B = \{ 1 \}, C = \{ 3 \}\);
- \(B = \{ 1 \}, C = \{ 2, 3 \}\);
- \(B = \{ 2 \}, C = \{ 1 \}\);
- \(B = \{ 2 \}, C = \{ 3 \}\);
- \(B = \{ 2 \}, C = \{ 1, 3 \}\);
- \(B = \{ 3 \}, C = \{ 1 \}\);
- \(B = \{ 3 \}, C = \{ 2 \}\);
- \(B = \{ 3 \}, C = \{ 1, 2 \}\);
- \(B = \{ 1, 2 \}, C = \{ 3 \}\);
- \(B = \{ 2, 3 \}, C = \{ 1 \}\); and
- \(B = \{ 1, 3 \}, C = \{ 2 \}\).
Explanation for the sample input/output #2
For rounds \(1\), \(2\), \(3\) and \(4\), there are \(0\), \(18\), \(0\), and \(2\) ways to build both decks, respectively.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 3 3
|
36
|
|
2
|
4
2 2 4 4
|
44
|
|
3
|
9
4 2 6 9 7 7 7 3 3
|
10858
|