配点 : 700 点
問題文
整数 N 。
集合 S 该值应乘以 S=\{1,2,\cdots,N\} 进行初始化。 之后, 重复以下操作,直至S 为空。 均匀随机化
- S 的元素 1 选择一项并 v 。 删除 S 减去 v 的所有倍数。
操作次数的预期值 请使用 \pmod{998244353} 找到它。
期待値 \pmod{998244353} 的定义
可以证明期望的期望值始终是有理数。另外,在这个问题的约束下,我们可以将该值转换为不可约分数 当表示为 \frac{P}{Q} 时,Q \neq 0 \pmod{998244353} 。因此,R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 的整数 选择 R 是唯一确定的。这个 请回答 R 。
制約
- 1 \leq N \leq 10^{10}
- 所有输入值均为整数
入力
输入是按以下格式从标准输入给出的。
N
出力
打印答案。
入力例 1
2
出力例 1
499122178
操作次数的预期值为 3/2 。 求放置超过
入力例 2
6
出力例 2
582309209
入力例 3
23
出力例 3
515759591
入力例 4
5000000000
出力例 4
64399530