용감한 유니콘 탐험가들

당신은 비밀 마법 결사 BSU(Brave Seekers of Unicorns)의 일원이다. BSU는 유니콘을 찾는 것을 좋아한다. 최근 BSU는 $k$개의 정수로 이루어진 배열 $a_1, a_2, \ldots, a_k$가 다음 조건을 모두 만족할 때 이 배열을 유니콘이라고 부르기로 했다.

• 배열은 비어 있지 않다 ($k > 0$).
• 연속한 세 원소의 비트 XOR이 0인 경우가 없다 ($1 \le i \le k - 2$인 모든 $i$에 대해 $a_i \oplus a_{i+1} \oplus a_{i+2} \ne 0$).
• 배열은 순증가한다 ($1 \le i \le k - 1$인 모든 $i$에 대해 $a_i < a_{i+1}$).
• 배열의 원소는 $1$ 이상 $n$ 이하의 정수다 ($1 \le i \le k$인 모든 $i$에 대해 $1 \le a_i \le n$).

예를 들어 $n = 10$일 때 배열 $[1, 4, 5, 9]$는 $1 \oplus 4 \oplus 5 = 0$이므로 유니콘이 아니지만, 배열 $[2, 4, 7, 9]$는 유니콘이다.

BSU의 대마법사가 당신에게 유니콘의 개수를 계산하라고 명령했다. 개수가 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구해야 한다.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 10^6$).

유니콘의 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.