Hide

Combinatorial 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
Difficulty 3.2medium
Statistics Show
Authors
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in