P17255 [Aboi 2077] It Was All a Dream!

> Become a **star** floating in the moonlit night. :::info[Noun Explanations] Define three types of **congruence subgroups** of $\text{SL}_2(\mathbb Z)$ modulo $N$: $\Gamma_0,\Gamma_1,\Gamma$: $$ \begin{aligned} \Gamma_0(N)&=\left\{\begin{bmatrix}a&b\\c&d\end{bmatrix}\in\text{SL}_2(\mathbb Z)\mathrel{\Bigg|}\begin{bmatrix}a&b\\c&d\end{bmatrix}\equiv\begin{bmatrix}*&*\\0&*\end{bmatrix}\pmod N\right\}\\ \Gamma_1(N)&=\left\{\begin{bmatrix}a&b\\c&d\end{bmatrix}\in\text{SL}_2(\mathbb Z)\mathrel{\Bigg|}\begin{bmatrix}a&b\\c&d\end{bmatrix}\equiv\begin{bmatrix}1&*\\0&1\end{bmatrix}\pmod N\right\}\\ \Gamma(N)&=\left\{\begin{bmatrix}a&b\\c&d\end{bmatrix}\in\text{SL}_2(\mathbb Z)\mathrel{\Bigg|}\begin{bmatrix}a&b\\c&d\end{bmatrix}\equiv\begin{bmatrix}1&0\\0&1\end{bmatrix}\pmod N\right\} \end{aligned} $$ Here, $*$ means there is no restriction. Define the **cusps** of a congruence subgroup $\Gamma$ as the equivalence classes of $\mathbb Q\cup\{\infty\}$ under the action of $\Gamma$. Here, for $\gamma=\begin{bmatrix}a&b\\c&d\end{bmatrix}\in\Gamma$, the action is defined as $\gamma(s)=\dfrac{as+b}{cs+d}$. In particular, $\gamma(\infty)=\dfrac ac$; if the denominator is $0$, then the value is $\infty$. Let $\varepsilon_\infty(\Gamma)$ be the number of cusps of the congruence subgroup $\Gamma$. :::

Given a positive integer $N$, for a given $G\in\{\Gamma_0,\Gamma_1,\Gamma\}$, compute $\displaystyle\sum_{n=1}^N\varepsilon_\infty(G(n))$, modulo $998244353$.

A single line with two integers $N,o$. Here $o=0,1,2$ correspond to $G=\Gamma_0,\Gamma_1,\Gamma$, respectively.

Output one integer, the value of the answer modulo $998244353$.

Subtask 1: $o=0$, $N\le10^{15}$. Subtask 2: $o=1$, $N\le10^{11}$. Subtask 3: $o=2$, $N\le10^{11}$. Translated by ChatGPT 5