問題文

座標平面上の、$x,y$ 座標がともに整数であるような点を格子点といいます。 $3$ 頂点が共に格子点であるような三角形の面積は、必ず $\frac12$ 以上になります。 以下、格子点からなる面積 $\frac12$ の三角形を最小格子三角形と呼びます。

牛子 さんは最小格子三角形が大好物です。 特に座標の大きなものを見つけたときに、大きな喜びを得ることができます。 牛子 さんが得られる喜びの総和を計算しましょう。

$N$ を正の整数とするとき、以下の値を計算してください。

• $3$ 点 $O(0,0), P(p_1,p_2), Q(q_1,q_2)$ が最小格子三角形をなすとき、その喜びを、$|p_1| + |p_2| + |q_1| + |q_2|$ で定めます。
• $OP\leqq \sqrt{N}$ かつ $OQ\leqq \sqrt{N}$ となる最小格子三角形 $OPQ$ に対する喜びの総和を、$998244353$ で割った余りを答えてください。

入力

$N$

• $N$ は正の整数で $1\leqq N\leqq 10^{12}$ を満たす。

出力

$1$ 行に、喜びの総和を $998244353$ で割った余りを出力してください。
最後に改行してください。

サンプル

1

8

25

1208

1000000

741919871