题目描述

黑板上写着一个整数 $X$。你可以任意次数（包括零次）地进行以下操作。

• 选择黑板上的一个整数 $x$。
• 擦掉一个 $x$，并写下两个新的整数 $\\lfloor \\frac{x}{2}\\rfloor$ 和 $\\lceil \\frac{x}{2}\\rceil$。

在进行操作后，求黑板上整数的乘积的最大可能值，对 $998244353$ 取模。

下面是 $\lfloor x/2\rfloor$ 和 $\\lceil x/2\\rceil$ 的解释。

对于实数 $x$，$\lfloor x\rfloor$ 表示不大于 $x$ 的最大整数，而 $\\lceil x\\rceil$ 表示不小于 $x$ 的最小整数。例如，以下内容成立。

• 对于 $x = 2$，我们有 $\lfloor \\frac{x}{2}\\rfloor = 1$ 和 $\\lceil \\frac{x}{2}\\rceil = 1$。
• 对于 $x = 3$，我们有 $\lfloor \\frac{x}{2}\\rfloor = 1$，$\\lceil \\frac{x}{2}\\rceil = 2$。

约束条件

• $1\\leq X \\leq 10^{18}$

输入

从标准输入给出以下格式的输入：

$X$

输出

打印操作后黑板上整数的乘积的最大可能值，对 $998244353$ 取模。

示例输入 1

15

示例输出 1

192

以下是一系列操作使得黑板上整数的乘积为 $192$。

• 黑板的初始状态是 $(15)$。
• 使用 $x = 15$ 进行一次操作，将黑板变为 $(7, 8)$。
• 使用 $x = 7$ 进行一次操作，将黑板变为 $(8, 3, 4)$。
• 使用 $x = 4$ 进行一次操作，将黑板变为 $(8, 3, 2, 2)$。
• 使用 $x = 8$ 进行一次操作，将黑板变为 $(3, 2, 2, 4, 4)$。

在这里，黑板上整数的乘积为 $3\\times 2\\times 2\\times 4\\times 4 = 192$。

示例输入 2

3

示例输出 2

3

不进行任何操作时，黑板上整数的乘积为 $3$。

示例输入 3

100

示例输出 3

824552442

进行操作后，黑板上整数的最大可能乘积是 $5856458868470016$，需要对 $998244353$ 取模。