AT_arc174_c [ARC174C] Catastrophic Roulette

有一个能等概率转出整数 $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$ 形式输出。

## 限制 - $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 翻译