P17255 [Aboi 2077] 全部夢だった！

> 月夜に浮かぶ　**星**になって :::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$ 取模的值。

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