题目描述

在赋格段的合奏中，自真冬的吉他与直巳的贝斯里倾泻出的音符不断相互追赶。

每枚音符都有一个正整数强度。追赶过程遵循欧几里得算法：设当前两枚音符的强度为 $c,d$，且 $c<d$。本轮中，较低的音符连续追赶较高的音符 $q=\lfloor d/c\rfloor$ 步，并记录步数 $q$；随后较高音符的强度变为 $d\bmod c$。若其中一枚音符强度变为 $0$，过程结束；否则重新比较两枚音符强度并继续。

对于步数为 $x$ 的一轮追赶，它在本轮激起的强度为 $h(x)$；经过一轮衰减后，留到下一轮的余响强度为 $g(x)$。若连续两轮追赶记录的步数依次为 $x,y$，则这两轮产生一次回响，其强度为 $r(x,y)=g(x)h(y)$。

设初始强度为 $a,b$（$b<a$）的两枚音符在追赶过程中依次记录到的步数为 $q_0,q_1,\ldots,q_k$，定义这段追赶的总回响为

$$f(a,b)=\sum_{i=0}^{k-1}g(q_i)h(q_{i+1}).$$

特别地，若只进行一轮，即 $k=0$，则规定 $f(a,b)=0$。

现在遍历所有满足 $1\le b<a\le N$ 且 $\gcd(a,b)=1$ 的有序对 $(a,b)$，求

$$S(N)=\sum_{\substack{1\le b<a\le N\\\gcd(a,b)=1}}f(a,b).$$

答案对 $998244353$ 取模。

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个整数 $g(1),g(2),\ldots,g(N)$。

第三行 $N$ 个整数 $h(1),h(2),\ldots,h(N)$。

输出格式

输出一行一个整数，表示 $S(N)\bmod 998244353$。

输入输出样例 #1

输入 #1

5
1 2 3 4 5
5 4 3 2 1

输出 #1

26

输入输出样例 #2

输入 #2

3
998244352 0 0
0 2 0

输出 #2

998244351

说明/提示

对于样例 1，产生非零贡献的互质对包括 $(3,2),(4,3),(5,2),(5,3),(5,4)$，贡献总和为 $26$。

对于样例 2，只有 $(3,2)$ 的欧几里得过程包含至少两轮，步数为 $1,2$，因此答案为 $g(1)h(2)=998244352\times2\equiv998244351\pmod{998244353}$。

数据范围

本题原题采用捆绑测试：

子任务	分值	$N\le$	特殊性质	时间限制
1	5	$10^3$	无	$1.2\text{s}$
2	10	$4\times10^4$
3	5	$10^5$	$g(x)=c,\ h(x)=d$
4		$1.5\times10^5$	$g(x)\equiv cx,\ h(x)=d$
5	8	$2\times10^5$	$g(x)\equiv cx,\ h(x)\equiv dx$
6	12		$h(x)=1$
7	10		无
8	15	$3\times10^5$		$1.7\text{s}$
9	30	$5\times10^5$		$3.2\text{s}$

对于全部数据，$1\le N\le5\times10^5$，且对任意 $1\le x\le N$，有 $0\le g(x),h(x)<998244353$。表格中的线性关系均在模 $998244353$ 意义下成立。

实现提示

整数除法和取模开销较大。原题提示可以预处理 double inv[d] = 1.0 / d，并使用 static_cast<int>(x * inv[d] + 1e-9) 计算 $\lfloor x/d\rfloor$。