AT_abc300_e [ABC300E] Dice Product 3

题目描述

你有一个等概率掷出 $1$ 到 $6$ 之间整数的骰子，以及一个初始为 $1$ 的整数。
只要你当前持有的整数小于 $N$，你就重复以下操作：

• 掷骰子，掷出的点数为 $x$。将你持有的整数乘以 $x$。

所有操作结束后，你持有的整数恰好等于 $N$ 的概率是多少？请将答案对 $998244353$ 取模后输出。

关于概率的 $998244353$ 取模：可以证明，所求概率一定是有理数。并且在本题的约束下，设其为互质的两个整数 $P, Q$ 的比值 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

输入格式

输入为一行，包含一个整数 $N$。

输出格式

输出所有操作结束后，你持有的整数恰好等于 $N$ 的概率对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

6

输出 #1

239578645

输入输出样例 #2

输入 #2

7

输出 #2

0

输入输出样例 #3

输入 #3

300

输出 #3

183676961

输入输出样例 #4

输入 #4

979552051200000000

输出 #4

812376310

说明/提示

限制

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

样例解释 1

操作结束前可能的一个过程如下：

• 初始时，持有的整数为 $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$。

样例解释 2

无论骰子如何掷，最终持有的整数都不可能等于 $7$。

由 ChatGPT 4.1 翻译