В этой задаче вам дано мультимножество \(S\). Необходимо по всем парам подмножеств \(A\) и \(B\) таких, что:
- \(B \subset A\);
- \(|B| = |A| - 1\);
- наибольший общий делитель элементов \(A\) равен единице;
найти сумму \(\sum_{x \in A}{x} \cdot \sum_{x \in B}{x}\) по модулю \(998\,244\,353\).
Выходные данные
В единственной строке выведите одно целое число — искомую сумму по модулю \(998\,244\,353\).
Примечание
Напомним, что мультимножество — это множество, в котором элементы могут повторяться несколько раз. \(|X|\) — мощность множества \(X\), количество элементов в нем.
\(A \subset B\) — множество \(A\) является подмножеством множества \(B\).
В первом примере \(B=\{1\}, A=\{1,2\}\) и \(B=\{2\}, A=\{1, 2\}\) дают произведение сумм \(1\cdot3 + 2\cdot3=9\). Все другие кандидаты на \(A\) и \(B\) не удовлетворяют требованиям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 1
2 1
|
9
|
|
2
|
4
1 1
2 1
3 1
6 1
|
1207
|
|
3
|
1
1 5
|
560
|