407975: GYM102956 C Brave Seekers of Unicorns
Memory Limit:0 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
C. Brave Seekers of Unicornstime limit per test1 secondmemory limit per test512 mebibytesinputstandard inputoutputstandard output
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$$$.
InputThe only line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$).
OutputPrint the number of unicorns modulo $$$998\,244\,353$$$.
ExamplesInput1Output
1Input
2Output
3Input
3Output
6Input
5Output
26Input
322Output
782852421