题目背景

月夜に浮かぶ　星になって

:::info[名词释义] 定义 $\text{SL}_2(\mathbb Z)$ 模 $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}$$

$*$ 表示无限制。

定义同余子群 $\Gamma$ 的尖点为 $\mathbb Q\cup\{\infty\}$ 在 $\Gamma$ 作用下的等价类。这里，对于 $\gamma=\begin{bmatrix}a&b\\c&d\end{bmatrix}\in\Gamma$，其作用定义为 $\gamma(s)=\dfrac{as+b}{cs+d}$，特别地有 $\gamma(\infty)=\dfrac ac$；若分母为 $0$ 则值为 $\infty$。

定义 $\varepsilon_\infty(\Gamma)$ 为同余子群 $\Gamma$ 的尖点数。 :::

题目描述

给定正整数 $N$，对于给定 $G\in\{\Gamma_0,\Gamma_1,\Gamma\}$，求 $\displaystyle\sum_{n=1}^N\varepsilon_\infty(G(n))$，对 $998244353$ 取模。

输入格式

一行两个整数 $N,o$，$o=0,1,2$ 分别对应 $G=\Gamma_0,\Gamma_1,\Gamma$。

输出格式

一行一个整数表示答案对 $998244353$ 取模的值。

10 0

28

10 1

44

10 2

158

提示

Subtask 1：$o=0$，$N\le10^{15}$；
Subtask 2：$o=1$，$N\le10^{11}$；
Subtask 3：$o=2$，$N\le10^{11}$。