题目描述

黑板上写有一个整数 $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

输入

15

输出

192

样例 2

输入

3

输出

3

样例 3

输入

100

输出

824552442

说明/提示

数据范围

• $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 翻译