← 返回题目列表

AtCoder · jsc2024_final_b

B. 删除多个

中文机器翻译题面 查看原题

配点 : 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