問題文

黒板にひとつの整数 $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$ で割った余りを出力します。