B - Squares Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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

  • 1 \leq x,y \leq N

  • x^2-y は平方数である．（特に，0 も平方数とする．）

制約

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

入力

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

N

出力

答えを出力せよ．

入力例 1

3

出力例 1

2

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

  • x=1,y=1

  • x=2,y=3

入力例 2

10

出力例 2

8

入力例 3

10000000000

出力例 3

52583544

Score : 500 points

Problem Statement

You are given an integer N. Find the number of pairs of integers (x, y) that satisfy the following conditions, modulo 998244353.

  • 1 \leq x,y \leq N.

  • x^2-y is a square number. (Assume 0 is also a square number.)

Constraints

  • 1 \leq N \leq 10^{12}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

3

Sample Output 1

2

We have the following two pairs.

  • x=1,y=1

  • x=2,y=3

Sample Input 2

10

Sample Output 2

8

Sample Input 3

10000000000

Sample Output 3

52583544