配点 : $500$ 点

問題文

整数 $N$ が与えられます． 以下の条件を満たす整数の組 $(x,y)$ の個数を $998244353$ で割った余りを求めてください．

• $1 \leq x,y \leq N$
• $x^2-y$ は平方数である．（特に，$0$ も平方数とする．）

制約

• $1 \leq N \leq 10^{12}$
• 入力される値はすべて整数である

入力

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

$N$

出力

答えを出力せよ．

3

2

以下の $2$ 通りが考えられます．

• $x=1,y=1$
• $x=2,y=3$

10

8

10000000000

52583544