問題文

太郎君ははじめ空の配列 $A=()$ を持っています。太郎君は以下の操作を $L$ 回行うことで、長さ $L$ の配列を完成させます。
ただし、操作回数 $L$ は $1 \leq L \leq N$ を満たす任意の整数とします。

• $1$ 以上 $N$ 以下の整数を $1$ つ選択し、その選択した値を $A$ の末尾に追加する。

完成した長さ $L$ の配列は以下の条件を満たす必要があります。

• $L$ を完成した配列の長さ、 $A_i$ を配列の $i$ 番目の数として、 $\gcd(A_1,A_2,…,A_L) \equiv 0 \pmod L$ を満たす。
  ただし、$\gcd(x) = x$ であるとする。

以上の操作によって作られる、条件を満たす配列は全部で何種類存在するかその種類数を求めてください。ただし、答えは非常に大きくなる場合があるので 、$998244353$ で割った余りを出力してください。

制約

• $N$ は整数
• $1 \leq N \leq 10^{11}$

入力

$N$

入力は以上の形式で標準入力から与えられる。

出力

答えを $998244353$ で割った余りを出力せよ。

サンプル

2

3

100

115612364