问题描述

有多少个由非负整数组成的集合$S$，其中整数的取值范围在$0$到$2^N-1$之间（包括两端），满足以下条件？以$998244353$为模输出计数。

• $S$的每一个非空子集$T$满足以下至少一条：
  • $T$中元素的数量是奇数。
  • $T$中元素的按位异或不等于$0$。

什么是按位异或（XOR）？

非负整数$A$和$B$的按位异或运算$A \\oplus B$定义如下：

• 当以二进制表示时，$A \\oplus B$的第$2^k$位（$k \\geq 0$）的数字为$1$，当且仅当$A$和$B$在该位上只有一个数字为$1$，否则为$0$。

例如，我们有$3 \\oplus 5 = 6$（二进制表示为$011 \\oplus 101 = 110$）。
一般来说，非负整数$p_1, p_2, p_3, \\dots, p_k$的按位异或运算定义为$(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$。我们可以证明，这个值与$p_1, p_2, p_3, \\dots, p_k$的顺序无关。

约束条件

• $1 \\le N \\le 2 \\times 10^5$
• 输入中的所有值均为整数。

输入

从标准输入读入输入数据，输入格式如下：

$N$

输出

打印答案。

示例输入1

2

示例输出1

15

满足条件的集合有$\\lbrace 0,2,3 \\rbrace$、$\\lbrace 1 \\rbrace$和空集$\\lbrace \\rbrace$。

而$\\lbrace 0,1,2,3 \\rbrace$不满足条件。

这是因为$\\lbrace 0,1,2,3 \\rbrace$的子集$\\lbrace 0,1,2,3 \\rbrace$的元素数量为偶数，它们的按位异或结果为$0$。

示例输入2

146

示例输出2

743874490