分数: 300 点
问题陈述
有一个整数 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.
约束
- 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.