В этой задаче вам дано мультимножество \(S\). Необходимо по всем парам подмножеств \(A\) и \(B\) таких, что:
найти сумму \(\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\).
Напомним, что мультимножество — это множество, в котором элементы могут повторяться несколько раз. \(|X|\) — мощность множества \(X\), количество элементов в нем.
\(A \subset B\) — множество \(A\) является подмножеством множества \(B\).
В первом примере \(B=\{1\}, A=\{1,2\}\) и \(B=\{2\}, A=\{1, 2\}\) дают произведение сумм \(1\cdot3 + 2\cdot3=9\). Все другие кандидаты на \(A\) и \(B\) не удовлетворяют требованиям.
2 1 1 2 1
9
4 1 1 2 1 3 1 6 1
1207
1 1 5
560
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач