Does It Divide?

题目描述

Alice and Bob are playing a number guessing game. First, Alice chooses an unknown positive integer $m$ uniformly at random from the interval $[1, n]$ as the secret number. Then, Bob needs to determine the exact value of $m$ by asking a series of questions. For each question, Bob can choose an arbitrary positive integer $x$ and ask Alice: "Is $m$ a multiple of $x$?" (formally, does $m \bmod x = 0$ hold?). Alice will answer truthfully with "Yes" or "No" to each question.

Bob wants to finish the game as quickly as possible because an upcoming Codeforces round is about to start. Therefore, he dynamically adjusts his questions based on Alice's previous answers to minimize the expected number of questions required to uniquely determine $m$.

Given the upper bound $n$, your task is to calculate this expected number of questions.

Output the answer modulo 998244353. Formally, let the exact answer be an irreducible fraction $\frac{P}{Q}$. You should output $P \cdot Q^{-1} \bmod 998244353$, where $Q^{-1}$ is the multiplicative inverse of $Q$ modulo 998244353.

输入格式

The only line contains a single integer $n$ ($1 \le n \le 10^7$) — the upper bound of the secret number.

输出格式

Output a single integer — the minimum expected number of questions Bob needs to uniquely determine $m$, modulo 998244353.

样例输入 #1

3

样例输出 #1

665496237

样例输入 #2

7

样例输出 #2

3

样例输入 #3

1

样例输出 #3

0