题面

请输出满足下述条件的集合 $S \in \{0,1,2,\ldots,2^N-1\}$ 的个数对 $998244353$ 取模后的结果。

• 对于所有 $S$ 的非空子集 $T$，均满足下列条件之一：

  • $\lvert T \rvert$ 为奇数；

  • $T$中所有元素的异或和不为 $0$。

何为异或?

输入

一行一个整数 $N$。

输出

一行一个整数，表示答案对 $998244353$ 取模后的结果。

数据范围&限制

$1 \le N \le 2 \times 10^5$，保证输入数据全为整数。