Hide

# Problem BCombinatorial Stanley Cup

You have always dreamt to get your name on the Stanley Cup, but you have never played hockey. A friend of yours heard of an alternative: the Combinatorial Stanley Cup! If you solve a single programming problem, you will get your name on this purely fictional trophy. What an opportunity!

The problem is simple: for a given $N$, find the number of odd coefficients in the binomial $(1+x)^ N$. Oh! There’s a catch: $N$ can be as big as $2$ billions!

## Input

The only line in the input is an integer $0 \leq N \leq 2\, 000\, 000\, 000$, the degree of the binomial $(1+x)^ N$ for which you need to determine how many of its coefficients are odd.

## Output

The number of odd coefficients.

Sample Input 1 Sample Output 1
0

1

Sample Input 2 Sample Output 2
1

2

CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show