分数: 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