F. Сумма по подмножествам
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этой задаче вам дано мультимножество $$$S$$$. Необходимо по всем парам подмножеств $$$A$$$ и $$$B$$$ таких, что:

  • $$$B \subset A$$$;
  • $$$|B| = |A| - 1$$$;
  • наибольший общий делитель элементов $$$A$$$ равен единице;

найти сумму $$$\sum_{x \in A}{x} \cdot \sum_{x \in B}{x}$$$ по модулю $$$998\,244\,353$$$.

Входные данные

В первой строке входного файла находится целое число $$$m$$$ ($$$1 \le m \le 10^5$$$) — количество различных элементов в мультимножестве $$$S$$$.

Далее идут $$$m$$$ строк, в каждой из которых по два целых числа $$$a_i$$$ и $$$freq_i$$$ ($$$1 \le a_i \le 10^5, 1 \le freq_i \le 10^9$$$). В мультимножестве $$$S$$$ элемент $$$a_i$$$ встречается $$$freq_i$$$ раз. Гарантируется, что все $$$a_i$$$ различны.

Выходные данные

В единственной строке выведите одно целое число — искомую сумму по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
2
1 1
2 1
Выходные данные
9
Входные данные
4
1 1
2 1
3 1
6 1
Выходные данные
1207
Входные данные
1
1 5
Выходные данные
560
Примечание

Напомним, что мультимножество — это множество, в котором элементы могут повторяться несколько раз. $$$|X|$$$ — мощность множества $$$X$$$, количество элементов в нем.

$$$A \subset B$$$ — множество $$$A$$$ является подмножеством множества $$$B$$$.

В первом примере $$$B=\{1\}, A=\{1,2\}$$$ и $$$B=\{2\}, A=\{1, 2\}$$$ дают произведение сумм $$$1\cdot3 + 2\cdot3=9$$$. Все другие кандидаты на $$$A$$$ и $$$B$$$ не удовлетворяют требованиям.