給定一個正整數 $N$。

請找出滿足 $1 \le a, b < 2^N$ 且符合以下條件的整數對 $(a, b)$ 的數量，並將結果對質數 $998244353$ 取模：

• 存在一個非退化三角形，其三邊長分別為 $a, b, a \oplus b$。

在此，對於整數 $x, y$，$x \oplus y$ 表示 $x$ 與 $y$ 的位元互斥或（bitwise XOR）。

輸入格式

第一行包含一個整數 $N$。($1 \le N \le 10^{18}$)

輸出格式

輸出滿足條件的整數對 $(a, b)$ 的數量，並對 $998244353$ 取模。

範例

輸入格式 1

2

輸出格式 1

0

輸入格式 2

5

輸出格式 2

390

說明

以第二個範例為例，$(a, b) = (13, 24)$ 滿足條件。因為 $a \oplus b = 13 \oplus 24 = 21$，存在一個邊長為 $13, 24, 21$ 的非退化三角形。

共有 $390$ 對滿足條件的整數對 $(a, b)$。

輸入格式 3

10000

輸出格式 3

851087540

說明

非負整數 $x, y$ 的位元互斥或 $x \oplus y$ 定義如下：

• 在 $x \oplus y$ 的二進位表示中，第 $2^k$ ($k \ge 0$) 位為 $1$ 當且僅當 $x$ 與 $y$ 的二進位表示中，第 $2^k$ 位恰有一個為 $1$；否則該位為 $0$。

例如，$3 \oplus 5 = 6$（二進位為 $011 \oplus 101 = 110$）。