Description

Format

Input

输入一个数 n。

Output

输出 tree(n) 中小 Z 第一步的必胜点个数，答案对 998244353 取模。

Samples

样例1

5

1

样例2

10

17

Limitation

1s, 1024KiB for each test case.