正の整数 $N$ が与えられます。 $1 \le a, b < 2^N$ を満たし、以下の条件を満たす整数の組 $(a, b)$ の個数を、素数 $998244353$ で割った余りで求めてください。

• 辺の長さが $a, b, a \oplus b$ である非退化な三角形が存在する。

ここで、整数 $x, y$ に対して $x \oplus y$ は $x$ と $y$ のビットごとの排他的論理和（XOR）を表します。

入力

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

$N$

ただし、$1 \le N \le 10^{18}$ です。

出力

条件を満たす整数の組 $(a, b)$ の個数を、素数 $998244353$ で割った余りで出力してください。

入出力例

入力 1

2

出力 1

0

入力 2

5

出力 2

390

入力 3

10000

出力 3

851087540

注記

例えば2番目の例において、$(a, b) = (13, 24)$ は条件を満たします。$a \oplus b = 13 \oplus 24 = 21$ であり、辺の長さが $13, 24, 21$ である非退化な三角形が存在するためです。 条件を満たす整数の組 $(a, b)$ は全部で $390$ 通り存在します。

非負の整数 $x, y$ のビットごとの XOR $x \oplus y$ は以下のように定義されます。

• $x \oplus y$ の二進数表現において、$2^k$ ($k \ge 0$) の位の数字は、$x$ と $y$ の二進数表現における $2^k$ の位の数字のうち、ちょうど一方が $1$ である場合に $1$ となり、それ以外の場合は $0$ となります。

例えば、$3 \oplus 5 = 6$ です（二進数では $011 \oplus 101 = 110$）。