시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 7 6 6 85.714%

문제

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

예제 출력 1

1

예제 입력 2

2

예제 출력 2

3

예제 입력 3

3

예제 출력 3

6

예제 입력 4

5

예제 출력 4

26

예제 입력 5

322

예제 출력 5

782852421