Given an undirected graph with $n - 1$ vertices, labeled $2 \sim n$. For all $2 \le u < v \le n$, an edge $(u, v)$ exists if and only if $v$ is a positive integer multiple of $u$. Let $f(u, v)$ denote whether $u$ and $v$ are connected: $f(u, v) = 1$ if $u$ and $v$ are connected, and $f(u, v) = 0$ otherwise. Calculate:

$$\left(\sum_{u = 2} ^ {n - 1} \sum_{v = u + 1} ^ n f(u, v) \cdot u \cdot v\right) \bmod {998244353}$$

Input

Read from standard input.

The input contains a single positive integer $n$. It is guaranteed that $4 \le n \le 10 ^ {11}$.

Output

Write to standard output.

Output a single non-negative integer representing the answer.

Examples

Input 1

4

Output 1

8

Note 1

$f(u, v) = 1$ if and only if $u = 2, v = 4$, so the answer is $2 \times 4 = 8$.

Input 2

6

Output 2

80

Note 2

All pairs $(u, v)$ satisfying $f(u, v) = 1$ are: $(2, 3), (2, 4), (2, 6), (3, 4), (3, 6), (4, 6)$.

Input 3

127

Output 3

23573971