201350: [AtCoder]ARC135 A - Floor, Ceil - Decomposition
Description
Score : $300$ points
Problem Statement
There is an integer $X$ written on a blackboard. You can do the operation below any number of times (possibly zero).
- Choose an integer $x$ written on the blackboard.
- Erase one $x$ from the blackboard and write two new integers $\lfloor \frac{x}{2}\rfloor$ and $\lceil \frac{x}{2}\rceil$.
Find the maximum possible product of the integers on the blackboard after your operations, modulo $998244353$.
What are $\lfloor \frac{x}{2}\rfloor$ and $\lceil \frac{x}{2}\rceil$?
For a real number $x$, $\lfloor x\rfloor$ denotes the largest integer not greater than $x$, and $\lceil x\rceil$ denotes the smallest integer not less than $x$. For example, the following holds.
- For $x = 2$, we have $\lfloor \frac{x}{2}\rfloor = 1$ and $\lceil \frac{x}{2}\rceil = 1$.
- For $x = 3$, we have $\lfloor \frac{x}{2}\rfloor = 1$, $\lceil \frac{x}{2}\rceil = 2$.
Constraints
- $1\leq X \leq 10^{18}$
Input
Input is given from Standard Input from the following format:
$X$
Output
Print the maximum possible product of the integers on the blackboard after your operations, modulo $998244353$.
Sample Input 1
15
Sample Output 1
192
Here is a sequence of operations that makes the product of the integers on the blackboard $192$.
- The initial state of the blackboard is $(15)$.
- An operation with $x = 15$ changes it to $(7, 8)$.
- An operation with $x = 7$ changes it to $(8, 3, 4)$.
- An operation with $x = 4$ changes it to $(8, 3, 2, 2)$.
- An operation with $x = 8$ changes it to $(3, 2, 2, 4, 4)$.
Here, the product of the integers on the blackboard is $3\times 2\times 2\times 4\times 4 = 192$.
Sample Input 2
3
Sample Output 2
3
Doing zero operations makes the product of the integers on the blackboard $3$.
Sample Input 3
100
Sample Output 3
824552442
The maximum possible product of the integers on the blackboard after your operations is $5856458868470016$, which should be printed modulo $998244353$.