Description

Given $N$, compute:

$$\sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\lfloor\frac{N}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{N}{j}\rfloor}[\gcd(i,j)=1][\gcd(p,q)=1]$$

Output the answer modulo $998244353$.

$[]$ is a conditional expression. When the statement inside the brackets is true, its value is $1$, otherwise it is $0$.

Input Format

A single line containing one integer $N$.

Output Format

Output one integer, the required answer modulo $998244353$.

50

104527

200

6664993

500000

835964450

10000000

503290049

100000000

712748411

1000000000

845640070

Hint

For all data, it is guaranteed that $1\le N\le 2\times10^9$. The time limit for all test points is $1\text{s}$, and the memory limit is $500\text{MB}$.

Test Point ID	$N$
$1$	$\le 100$
$2$	$\le 400$
$3,4,5,6$	$\le10^6$
$7,8$	$\le 2\times10^7$
$9$	$\le 2\times10^8$
$10$	$\le 2\times10^9$

This problem could actually have been made into multiple test cases in one input. But the kind problem setter decided to use only one test case, to give you more chances to get partial points.

The idea came from @Fee_cle6418. The statement, official solution, and testdata come from @FangZeLi.

Translated by ChatGPT 5