我们称一个具有 $n$ 个顶点的无向图是“好的”，如果对于所有 $1 \le u, v \le n$，在 $u$ 和 $v$ 之间至少存在一条路径 $u = x_1, x_2, \dots, x_m = v$，使得 $\gcd(u, v) = \gcd(x_1, x_2, \dots, x_m)$。
我们称一个具有 $n$ 个顶点的无向图是“完美的”，如果它是“好的”且该图的边数最少。也就是说，任何其他具有 $n$ 个顶点的“好的”图的边数都不会少于该图。
你需要计算具有 $n$ 个顶点的“完美的”图的数量。
由于答案可能非常大，你只需要输出其对 $998\,244\,353$ 取模的结果。
输入格式
输入仅包含一个整数 $n$ ($2 \le n \le 10^{11}$)，表示你需要计算的“完美的”图的顶点数。
输出格式
输出仅包含一个整数，表示答案对 $998\,244\,353$ 取模的结果。
样例
样例输入 1
4
样例输出 1
8