P17229 [Math×Girl²] Eroica Variations Op.35

> Then, the final variation arrived. In C minor, as vast as the ocean in a deep night after a storm. Thunder, gradually fading away yet echoing again and again in the depths of the clouds. Whispers from the deep sea. A low G, plucked by the fingers of my right hand, stretching into the infinite distance. And then, dawn came as the clouds parted and the sun appeared. I listened, intoxicated, to the hazy resonance lingering in my abdomen, while loosening my left hand. After that, my sweaty hand gripped the neck again. > > It is a fugue. I have finally reached here. > > After I poured out my delusions, burning in pitch black, what appeared was an ensemble full of infinite rationality—clear and transparent like crystal. I carved out the very first note of the opening. From the simple four notes that sounded when this war began, the main theme of the fugue started to flow. Four measures later, Mafuyu chased after me as I began to run. Into the two melodies that would never intersect, and could never possibly touch, a third melody like a mirage joined in. Who on earth played it—of course, Mafuyu and I. We passed fragments of the melody to each other, slowly stacking them into a clear melodic line, as if a third person were performing on the spot. Even I could not make sense of it—I was merely playing the score written by senpai, and Mafuyu instantly read the intention of the piece and kept responding. That is all I can think. But can something like this really be done? Without saying a word, can hearts be conveyed through music alone—can such a miracle happen? Or will this miracle disappear the moment I open my eyes— > > ...It gradually disappeared. > > I stopped moving my fingers. > > Mafuyu’s melody, which should have been chasing after mine, suddenly vanished. > > The illusory warmth of Mafuyu that I had felt on my back also disappeared. > > I turned around. From the other side of the door came a creak—faint noise caused by guitar feedback. This problem is adapted from [Project Euler 433](https://projecteuler.net/problem=433).

::::info[Formal Statement]{open} You are given a positive integer $N$ and the values of two integer-valued functions $g,h:\{1,2,\ldots,N\}\to\mathbb Z$. For integers $x,y$ satisfying $1\le y0. \end{cases} $$ Compute $$ S(N)= \sum_{\substack{1\le b

The first line contains a positive integer $N$. The second line contains $N$ integers, in order: $g(1), g(2), \dots, g(N)$. The third line contains $N$ integers, in order: $h(1), h(2),\dots, h(N)$.

Output one integer in a single line, representing $S(N)\bmod 998244353$.

### Sample Explanation **For Sample #1**: Among all coprime pairs $(a,b)$ ($1\le b