题目描述

提供 一句话题意 阅读。

某地有 $n$ 个小朋友，每个小朋友都有一个独特的 idea，其中第 $i$ 个小朋友的 idea 的 编号 为 $i$。老师让这个每一个小朋友在一组编号分别为 $1\sim n$ 的卡片中随机抽一个，抽完后把卡片放回去，这个小朋友会和编号为卡片上数字的小朋友交换 idea（交换指两人把所有自己知道的 idea 告诉对方）。因为自己和自己交换 idea 在他们眼中也许是一件很傻的事情，所以如果卡片上的编号与自己的相同，他将再抽一次（此时他已经把卡片放回去了），直到编号不是自己的为止。

不久，每个小朋友都抽完了一遍，每个小朋友将把收集到的所有 idea 出成一场比赛，因为有 idea 的交换，有很多比赛之间都是有联系的。

如果两场比赛中存在 idea 相同的题目，我们认为这两场比赛是有联系的。「联系」具有传递性：如果比赛 $\mathbf A$、$\mathbf B$ 有联系，比赛 $\mathbf B$、$\mathbf C$ 有联系，则比赛 $\mathbf A$、$\mathbf C$ 也有联系。为了避免理解错误，在这举一个例子：

若仅有四场比赛：比赛一出现了 idea $1$、$2$；比赛二出现 idea $2$、$5$ ；比赛三出现 idea $3$、$5$、$8$，比赛四出现 idea $4$、$7$。则比赛一、二之间有直接联系。比赛一、三之间虽然没有公共 idea，但它们之间是有联系的。比赛四与其他所有比赛没有联系。

而所有有联系的比赛都将属于同一个比赛集，没有联系的比赛处在不同的比赛集。

上例中比赛一、二、三属于一个比赛集，比赛四属于另一个。

求所有人抽球卡片的次数和的期望 $E_0$ 和比赛集的个数 $s$ 的期望 $E_1$。

---

一句话题意：

对于每个点 $i$ 随机与 $[1,n]$ 中的一点连无向边，若连向自己，则保留该边并再次连边，一直重复至连到别的点上为止，求边数与连通块个数期望。

输入格式

输入一行一个正整数 $n$。

输出格式

第一行输出一个数 $E_0$ ，第二行输出一个数 $E_1$ ，可以证明它们都是有理数。

为了避免精度误差，您只需要输出它们对质数 $998244353$ 取模的结果即可，如果您不会分数取模，您可以查找关于费马小定理与乘法逆元的相关资料。

如果输出格式错误或两问答案均错误，该测试点得 $0$ 分；

如果仅答对第一问，该测试点得 $3$ 分；

如果仅答对第二问，该测试点得 $7$ 分；

如果两问均正确，该测试点得 $10$ 分。

请务必输出两个整数。

2

4
1

7

166374067
539688692

提示

---

样例解释

样例解释一

• 每个小朋友摸卡片次数为 $1$ 的概率为 $\dfrac{1}{2}$，摸卡片次数为 $2$ 的概率为 $\dfrac{1}{4}$，摸卡片次数为 $i$ 的期望次数为 $\dfrac{1}{2^i}$，期望摸卡片次数为 $2$，总摸卡片次数为 $4$。

• $1$ 号小朋友一定会和 $2$ 号小朋友交换 idea，所以他们出的比赛之间一定是属于同一个比赛集。$E_1=1$。

样例解释二

• 第一问取模前的答案为 $\dfrac{49}{6}$。

• 第二问取模前的答案为 $\dfrac{2245}{1944}$。

---

数据范围

测试点编号	$n$	测试点编号	$n$
$1$	$\leq 3$	$5$	$\leq 1000$
$2$	$\leq 5$	$6$	$\leq 2000$
$3$	$\leq 9$	$7\sim8$	$\leq 5000$
$4$	$\leq 12$	$9\sim 10$	$\leq10^4$

对于 $100\%$ 的数据，有 $2\leq n\leq10^4$。

---