骰子乘积 3

题目描述

你有一个整数 $1$ 和一个骰子,掷出 $1$ 到 $6$(含)之间的每个整数的概率均等。

只要你的整数严格小于 $N$,就重复以下操作:

掷一次骰子。如果掷出 $x$,就把你的整数乘以 $x$。

求你的整数最终成为 $N$ 的概率,对 $998244353$ 取模。

如何对 $998244353$ 取模求概率?

可以证明所求概率总是有理数。此外,在本问题的约束下,当该值表示为两个互质的整数 $P$ 和 $Q$ 之比 $\frac{P}{Q}$ 时,可以证明存在唯一的整数 $R$,满足 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。求出这个 $R$。

输入格式

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

$N$

输出格式

输出你的整数最终成为 $N$ 的概率对 $998244353$ 取模的结果。

样例

6

239578645

一种可能的操作过程如下。

初始时,你的整数为 $1$。

掷一次骰子,掷出 $2$。你的整数变为 $1 \times 2 = 2$。

掷一次骰子,掷出 $4$。你的整数变为 $2 \times 4 = 8$。

此时你的整数不小于 $6$,因此操作结束。

你的整数最终为 $8$,不等于 $N = 6$。

你的整数最终成为 $6$ 的概率为 $\frac{7}{25}$。由于 $239578645 \times 25 \equiv 7 \pmod{998244353}$,因此输出 $239578645$。

7

0

无论骰子掷出什么,你的整数都永远不会成为 $7$。

300

183676961

979552051200000000

812376310

数据范围

• $2 \leq N \leq 10^{18}$
• $N$ 为整数。