题目描述

请求出由 $[0,2^N)$ 的非负整数组成的集合 $S$ 中，满足以下条件的集合的个数对 $998244353$ 取模的结果。

• $S$ 的任意非空子集 $T$ 都满足以下两者之一：
  • $T$ 的元素个数为奇数；
  • $T$ 所有元素的 $\mathrm{XOR}$ 不为 $0$。

::::info[什么是 $\mathrm{XOR}$？]

$\mathrm{XOR}$ 指的是非负整数 $A, B$ 的按位异或，记作 $A \oplus B$，定义如下：

• $A \oplus B$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数，如果 $A, B$ 的二进制表示中该位只有一个为 $1$，则该位为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制为：$011 \oplus 101 = 110$）。 一般地，$k$ 个整数 $p_1, p_2, p_3, \dots, p_k$ 的按位 $\mathrm{XOR}$ 定义为 $((\dots((p\_1 \oplus p\_2) \oplus p\_3) \oplus \dots) \oplus p\_k)$，并且可以证明，这个值与 $p_1, p_2, \dots, p_k$ 的顺序无关。

输入格式

输入为以下格式，从标准输入读取。

$N$

输出格式

请输出答案。

样例 1

输入

2

输出

15

样例 2

输入

146

输出

743874490

说明/提示

限制

• $1 \leq N \leq 2 \times 10^5$
• 输入均为整数。

样例解释 1

$\lbrace 0,2,3 \rbrace$、$\lbrace 1 \rbrace$、$\lbrace \rbrace$ 等集合满足条件。$\lbrace 0,1,2,3 \rbrace$ 不满足条件，因为它的子集 $\lbrace 0,1,2,3 \rbrace$ 的元素个数为偶数，且所有元素的 $\mathrm{XOR}$ 为 $0$。

由 ChatGPT 4.1 翻译