配点 : $300$ 点

問題文

黒板にひとつの整数 $X$ が書かれています。あなたは次の操作を、何度でも行うことができます（一度も行わなくてもよいです）。

• 黒板に書かれている整数 $x$ をひとつ選ぶ。
• $x$ をひとつ黒板から消去し、新たに $\lfloor \frac{x}{2}\rfloor$ と $\lceil \frac{x}{2}\rceil$ をひとつずつ黒板に書く。

操作後の黒板に書かれている整数すべての積としてありうる最大値を、$998244353$ で割った余りを答えてください。

制約

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

入力

入力は以下の形式で標準入力から与えられます。

$X$

出力

操作後の黒板に書かれている整数すべての積としてありうる最大値を、$998244353$ で割った余りを出力してください。

15

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$ です。

3

3

操作を一度も行わないことで、黒板に書かれている整数すべての積を $3$ にすることが可能です。

100

824552442

操作後の黒板に書かれている整数すべての積としてありうる最大値は、$5856458868470016$ です。これを $998244353$ で割った余りを出力します。