给定一个正整数 $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$）。