题目描述

你有一个初始整数 $1$ 和一个骰子，该骰子显示 $1$ 到 $6$ 之间的整数（包括 $1$ 和 $6$），每个数出现的概率相等。
当你的整数严格小于 $N$ 时，重复以下操作：

• 投掷骰子。如果它显示 $x$，则将你的整数乘以 $x$。

找出你的整数最终变为 $N$ 的概率（对 $998244353$ 取模）。

如何求解取模 $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$

输出

输出你的整数最终变为 $N$ 的概率（对 $998244353$ 取模）。

---

示例输入 1

6

示例输出 1

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$。

---

示例输入 2

7

示例输出 2

0

无论骰子显示什么，你的整数永远不会变为 $7$。

---

示例输入 3

300

示例输出 3

183676961

---

示例输入 4

979552051200000000

示例输出 4

812376310