Thue-Morse Sequence N-th Term

Compute the n-th term of the Thue-Morse sequence. The sequence is defined recursively as follows: start with \(a(0)=0\), and for each \(n\geq 0\), the term \(a(n)\) is determined by the parity of the number of 1's in the binary representation of \(n\). Specifically, if the number of 1's is even, then \(a(n)=0\); if odd, then \(a(n)=1\).

This sequence can also be generated by starting with 0 and, at each step, appending the binary complement of the sequence obtained so far.

inputFormat

The input consists of a single non-negative integer \(n\) (0-based index) provided via standard input.

outputFormat

Print a single integer representing the n-th term of the Thue-Morse sequence to standard output.

0

0