你是 Brave Seekers of Unicorns (BSU) 这个秘密魔法组织的成员。BSU 热衷于寻找独角兽（unicorn）。最近，他们约定将一个包含 $k$ 个整数的数组 $a_1, a_2, \dots, a_k$ 称为独角兽，如果它满足以下条件：

• 数组非空（$k > 0$）；
• 不存在三个连续元素的按位异或和为零（对于所有 $1 \le i \le k - 2$，满足 $a_i \oplus a_{i+1} \oplus a_{i+2} \neq 0$）；
• 数组严格递增（对于所有 $1 \le i \le k - 1$，满足 $a_i < a_{i+1}$）；
• 数组中的元素均为 $1$ 到 $n$ 之间的整数（对于所有 $1 \le i \le k$，满足 $1 \le a_i \le n$）。

例如，当 $n = 10$ 时，数组 $[1, 4, 5, 9]$ 不是独角兽，因为 $1 \oplus 4 \oplus 5 = 0$，而数组 $[2, 4, 7, 9]$ 是一个独角兽。

BSU 的大导师命令你计算独角兽的数量。由于数量可能非常大，你必须将其对 $998\,244\,353$ 取模。

输入格式

唯一的一行包含一个整数 $n$（$1 \le n \le 10^6$）。

输出格式

输出独角兽的数量，对 $998\,244\,353$ 取模。

样例

输入 1

1

输出 1

1

输入 2

2

输出 2

3

输入 3

3

输出 3

6

输入 4

5

输出 4

26

输入 5

322

输出 5

782852421