题目描述

有一个能等概率转出整数 $1,2,\dots,N$ 的轮盘。
两个人用它进行如下游戏：

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

请分别求出先手和后手在游戏结束前需要支付的罚金的期望值，并对 $998244353$ 取模后输出。

期望值 $\bmod\ 998244353$ 的定义：本题中要求的期望值一定是有理数。并且，在本题的约束下，设期望值为既约分数 $\frac{y}{x}$，保证 $x$ 不会被 $998244353$ 整除。

此时，存在唯一的整数 $z$，满足 $0 \leq z \leq 998244352$ 且 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入格式

输入通过标准输入按以下格式给出。

$N$

输出格式

请输出两个整数。
第一个为先手支付的罚金期望值，第二个为后手支付的罚金期望值，均以 $\bmod\ 998244353$ 形式输出。

样例 1

输入

1

输出

0 0

样例 2

输入

2

输出

332748118 665496236

样例 3

输入

3

输出

174692763 324429416

说明/提示

限制

• $N$ 是满足 $1 \leq N \leq 10^6$ 的整数。

样例解释 1

本样例中 $N=1$。先手转动轮盘必定转出 $1$，游戏立即结束。因此，先手和后手支付的罚金期望值均为 $0$。

样例解释 2

本样例中 $N=2$。游戏的一种可能流程如下：

• 先手转动轮盘，转出 $2$，什么都不会发生。
• 后手转动轮盘，转出 $2$，后手支付 $1$ 日元罚金。
• 先手转动轮盘，转出 $2$，先手支付 $1$ 日元罚金。
• 后手转动轮盘，转出 $1$，什么都不会发生。
• 此时 $1,2$ 都至少出现过一次，游戏立即结束。
• 在这种情况下，先手支付 $1$ 日元罚金，后手支付 $1$ 日元罚金。 可以证明，先手支付的罚金期望值为 $\frac{1}{3}$ 日元，后手支付的罚金期望值为 $\frac{2}{3}$ 日元。

由 ChatGPT 4.1 翻译