给你一个多重集 $$$S$$$。在所有子集对 $$$A$$$ 和 $$$B$$$ 上,使得:
- $$$B \子集 A$$$;
- $$$|B| =|A| - 1$$$;
- $$$A$$$ 中所有元素的最大公约数等于 1;
求 $$$\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$$$)。元素 $$$a_i$$$ 在多重集合 $$$S$$$ 中出现 $$$freq_i$$$ 次。所有 $$$a_i$$$ 都是不同的。
输出
打印所需的总和,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
2 1 1 2 1
输出 #1
9
输入 #2
4 1 1 2 1 3 1 6 1
输出 #2
1207
输入 #3
1 1 5
输出 #3
560
注意
多重集是允许元素重合的集合。 $$$|X|$$$ 是集合 $$$X$$$ 的基数,即其中元素的数量。
$$$A \子集 B$$$:集合 $$$A$$$ 是集合 $$$B$$$ 的子集。
在第一个示例中,$$$B=\{1\}、A=\{1,2\}$$$ 和 $$$B=\{2\}、A=\{1, 2\}$$$ 的乘积等于 $$$1\cdot3 + 2\cdot3=9$$$。其他对 $$$A$$$ 和 $$$B$$$ 不满足给定的约束。