/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 に対して，x 以下の最大の整数を \lfloor x\rfloor、x 以上の最小の整数を \lceil x\rceil と書きます。したがって例えば以下が成り立ちます。
- 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 で割った余りを出力します。
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.