该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

这个题目，我是真不知道怎么编背景了。
求出满足如下条件的序列个数：
1. 非空，严格递增，且每个数为\(1 \sim n\)之间的整数。
2. 不存在相邻的三个元素，其异或和为零。

Format

Input

仅一行一个整数\(n(1<=n<=10^6)\)。

Output

一行一个整数表示答案除以\(998244353\)所得余数。

Sample 1

Input

5

Output

26

Sample 2

Input

322

Output

782852421

Limitation

1s, 512MB for each test case.

Source

Vijos Original