시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 26 | 19 | 16 | 69.565% |
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:
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