題目描述

俾定一個正整數 $N$。

求滿足 $1 \le a, b < 2^N$ 且滿足以下條件嘅整數對 $(a, b)$ 嘅數量，結果對質數 $998244353$ 取模：

• 存在一個以 $a, b, a \oplus b$ 為邊長嘅非退化三角形。

其中，對於整數 $x, y$，$x \oplus y$ 表示 $x$ 同 $y$ 嘅按位異或。

輸入格式

第一行包含一個整數 $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$ 為邊長嘅非退化三角形。

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

範例輸入 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$）。