Background

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$. :::

Problem Description

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$.

Input Format

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

Output Format

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

10 0

28

10 1

44

10 2

158

Hint

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