AT_arc135_a.[ARC135A] Floor, Ceil - Decomposition

黑板上写有一个整数 $X$。你可以进行如下操作任意多次（也可以一次都不进行）：

• 从黑板上选择一个整数 $x$。
• 将 $x$ 从黑板上擦去，并在黑板上分别写下 $ \lfloor \frac{x}{2} \rfloor $ 和 $ \lceil \frac{x}{2} \rceil $。

请输出操作结束后，黑板上所有整数的乘积可能取得的最大值，并将其对 $998244353$ 取余后的结果输出。

$ \lfloor \frac{x}{2} \rfloor $ 和 $ \lceil \frac{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 $。

输入通过标准输入给出，格式如下：

$X$

请输出操作结束后，黑板上所有整数的乘积可能取得的最大值对 $998244353$ 取余的结果。

数据范围

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

样例解释 1

例如，可以按如下方式操作，使黑板上所有整数的乘积为 $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$。

样例解释 3

操作结束后，黑板上所有整数的乘积可能取得的最大值为 $5856458868470016$。将其对 $998244353$ 取余后输出。

由 ChatGPT 4.1 翻译