407975: GYM102956 C Brave Seekers of Unicorns

You are a member of the Brave Seekers of Unicorns (BSU), the secret magical order. The BSU is fond of seeking unicorns. Recently, they have agreed to call an array $$$a_1, a_2, \ldots, a_k$$$ of $$$k$$$ integers a unicorn if it satisfies the following conditions:

• the array is not empty ($$$k > 0$$$);
• there are no three consecutive elements with their bitwise XOR equal to zero ($$$a_i \oplus a_{i+1} \oplus a_{i+2} \ne 0$$$ for all $$$1 \le i \le k - 2$$$);
• the array is strictly increasing ($$$a_i < a_{i+1}$$$ for all $$$1 \le i \le k - 1$$$);
• the elements of the array are integers between $$$1$$$ to $$$n$$$, inclusively ($$$1 \le a_i \le n$$$ for all $$$1 \le i \le k$$$).

For example, if $$$n = 10$$$, then the array $$$[1, 4, 5, 9]$$$ is not a unicorn because $$$1 \oplus 4 \oplus 5 = 0$$$, but the array $$$[2, 4, 7, 9]$$$ is a unicorn.

The Grand Master of the BSU has commanded you to calculate the number of unicorns. Since the number can be pretty large, you must compute it modulo $$$998\,244\,353$$$.

The only line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

Print the number of unicorns modulo $$$998\,244\,353$$$.

1

1

2

3

3

6

5

26

322

782852421