Points: $500$ points

问题陈述

有一个轮盘，它以相等的概率产生从 $1,2,\dots,N$ 的整数。 两个玩家使用它来玩以下游戏：

• 玩家轮流旋转轮盘。
  • 如果产生的整数之前没有出现过，则什么也不会发生。
  • 否则，旋转轮盘的玩家需要支付1日元的罚款。
• 当所有 $N$ 个整数至少出现一次时，游戏立即结束。

对于第一和第二个玩家，找出游戏结束前支付的罚款金额的期望值，对 $998244353$ 取模。

关于 $998244353$ 模下的期望值

可以证明，这个问题中寻求的期望值总是有理数。此外，在这个问题的约束下，当期望值表示为不可约分数 $\frac{y}{x}$ 时，保证 $x$ 不能被 $998244353$ 整除。

现在，存在一个唯一的整数 $z$，介于 $0$ 和 $998244352$（包括），使得 $xz \equiv y \pmod{998244353}$。提供这个 $z$ 作为答案。

以上为大语言模型 kimi 翻译，仅供参考。

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$.

Sample Input 1

1

Sample Output 1

0 0

In this input, $N=1$.
When the first player spins the roulette, it always produces $1$, ending the game immediately.
Thus, the expected values of the amounts of the fines paid by the first and second players are both $0$.

Sample Input 2

2

Sample Output 2

332748118 665496236

In this input, $N=2$. Here is a possible progression of the game:

• The first player spins the roulette, and it produces $2$. Nothing happens.
• The second player spins the roulette, and it produces $2$. The second player pays a fine of $1$ yen.
• The first player spins the roulette, and it produces $2$. The first player pays a fine of $1$ yen.
• The second player spins the roulette, and it produces $1$. Nothing happens.
• At this point, both $1$ and $2$ have appeared at least once, so the game immediately ends.
• In this progression, the amount of the fine paid by the first player is $1$ yen, and the amount of the fine paid by the second player is also $1$ yen.

It can be shown that the expected value of the amount of the fine paid by the first player is $\frac{1}{3}$ yen, and the expected value of the amount of the fine paid by the second player is $\frac{2}{3}$ yen.

Sample Input 3

3

Sample Output 3

174692763 324429416