Problem Statement

There is a roulette that produces an integer from $1,2,\dots,N$ with equal probability. Two players use it to play the following game:

• The players take turns spinning the roulette.
• If the produced integer has not appeared before, nothing happens.
  • Otherwise, the player who spun the roulette pays a fine of $1$ yen.
• The game immediately ends when all of the $N$ integers have appeared at least once.

For each of the first and second players, find the expected value of the amount of the fine paid before the game ends, modulo $998244353$.

On expected values modulo $998244353$ It can be proved that the expected values sought in this problem are always rational numbers. Furthermore, under the constraints of this problem, when the expected values are expressed as irreducible fractions $\frac{y}{x}$, it is guaranteed that $x$ is not divisible by $998244353$. Now, there is a unique integer $z$ between $0$ and $998244352$, inclusive, such that $xz \equiv y \pmod{998244353}$. Provide this $z$ as the answer.

Constraints

• $N$ is an integer such that $1 \le N \le 10^6$.

Input

The input is given from Standard Input in the following format:

N

Output

Print two integers as the answer. The first is the expected value of the amount of the fine paid by the first player, and the second is the expected value of the amount of the fine paid by the second player, represented as integers modulo $998244353$.