题目描述

黒板にひとつの整数 $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$。

输入格式

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

$X$

输出格式

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

15

192

3

3

100

824552442

提示

制約

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

Sample Explanation 1

例えば次のように操作を行うことで、黒板に書かれている整数すべての積を $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$ です。

Sample Explanation 2

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

Sample Explanation 3

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