题目描述

定义 $f(n) = \sum_{i=0}^{n-1} [i^2 \equiv 1 \pmod{n}]$，其中 $n \in \mathbb{N}^*$。

其中 $[a]$ 表示当 $a$ 为真时值为 1，否则为 0。

求 $\sum_{i=1}^{k} f(i)$ 对 998244353 取模的余数。

输入格式

一行一个正整数 ( k )。

输出格式

一行一个正整数表示答案对 998244353 取模的结果。

样例

input 1

1

output 1

1

input 2

3

output 2

4

input 3

999999999

output 3

197239157

数据范围

$1\le k \le 10^9$