Description

在其中一个世界，欧提努斯给了当麻 $1 \sim n$ 的所有整数。

当麻要将这些数划分成三个集合（可以为空），要求任意两个属于不同集合的元素之和不在剩下的那个集合之内。集合之间是无序的。

如：$\{4\}$, $\{2, 6\}$, $\{1, 3, 5\}$ 是 $n = 6$ 时的合法划分方案。而 $\{1, 2, 4\}$, $\{3, 6\}$, $\{5\}$ 却不是，由于 $2 + 3 = 5$。

欧提努斯要求当麻计算这样的划分的方案数对 $998244353$ 取模的值，否则就杀死他。

当麻没学过 OI，于是他不会做。但好在，这个世界里还有你的存在，请帮助他求出方案数。

Input Format

一行一个正整数 $n$。

Output Format

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

11

1092

4

9

514

653467211

Hint

数据范围与约定

• Subtask 1（4%）：$n \leq 10$；
• Subtask 2（13%）：$n \leq 40$；
• Subtask 3（17%）：$n \leq 3000$；
• Subtask 4（21%）：$n \leq 10^6$；
• Subtask 5（22%）：$n \leq 10^9$；
• Subtask 6（23%）：$n \leq 2 \times 10^{10}$；