← 返回题目列表

AtCoder · abc300_e

H. 骰子产品 3

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

分数: 500 点

问题陈述

你有一个整数 1 和一个显示之间整数的骰子 1 和 6 (含)等概率。
当您的整数严格小于时,您重复以下操作 N:

  • 掷骰子。 如果显示 x,将您的整数乘以 x.

求概率,模 998244353,你的整数最终是 N.

如何求概率模 998244353? 我们可以证明所求的概率总是有理数。 此外,在该问题的约束下,当该值表示为 \frac{P}{Q} 具有两个互质整数 P 和 Q,我们可以证明有一个唯一的整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。 找到这个 R.

约束

  • 2 \leq N \leq 10^{18}
  • N 是一个整数。

输入

输入由标准输入按以下格式给出:

N

输出

打印概率,模数 998244353,你的整数最终是 N.


示例输入 1

6

示例输出 1

239578645

可能的过程之一如下。

  • 最初,您的整数是 1.
  • 你掷骰子,结果显示 2。 你的整数变成 1 \times 2 = 2.
  • 你掷骰子,结果显示 4。 你的整数变成 2 \times 4 = 8.
  • 现在你的整数不小于 6,因此您终止该过程。

你的整数最终是 8,不等于 N = 6.

你的整数最终成为的概率 6 is \frac{7}{25}。 自从 239578645 \times 25 \equiv 7 \pmod{998244353},打印 239578645.


示例输入 2

7

示例输出 2

0

无论骰子显示什么,你的整数永远不会成为 7.


示例输入 3

300

示例输出 3

183676961

示例输入 4

979552051200000000

示例输出 4

812376310