Gew 正在寻找满足以下性质的“Eminor”序列 $[a_1, a_2, \dots, a_m]$：

• 序列非空 ($m \ge 1$)；
• $1 \le a_i \le 2^n - 1$；
• 数组严格递增（对于每个 $i \le m - 1$，都有 $a_i < a_{i+1}$）；
• 不存在三个连续元素，使得它们的按位异或和为零（对于每个 $i \le m - 2$，都有 $a_i \oplus a_{i+1} \neq a_{i+2}$。其中 $\oplus$ 表示按位异或运算）。

现在，Gew 想知道有多少个“Eminor”序列。由于“Eminor”序列的数量可能非常大，你只需要输出答案对 $998\,244\,353$ 取模的结果。

输入格式

输入包含一个整数 $n$ ($1 \le n \le 10^6$)。

输出格式

输出一个整数，表示“Eminor”序列的数量，对 $998\,244\,353$ 取模。

样例

样例输入 1

1

样例输出 1

1

样例输入 2

2

样例输出 2

6

样例输入 3

3

样例输出 3

91

说明

对于第二个测试用例，以下是 6 个可能的“Eminor”序列：

• $[1]$
• $[2]$
• $[3]$
• $[1, 2]$
• $[1, 3]$
• $[2, 3]$