Pascal's Triangle

Pascal's triangle is an infinite triangle of numbers that looks like this:

The rows of Pascal's triangle are numbered from zero, and the numbers in each row are also numbered from zero. Row zero contains a single number, one, and each subsequent row contains one more number than the previous row. The zeroth and last numbers of each row are one, and each of the others equals the sum of the two numbers above it in the previous row.

Thus row $i$ contains $i + 1$ numbers. If the $j$-th element of row $i$ is denoted $a_{i,j}$, then $a_{i,j} = a_{i - 1,j - 1} + a_{i-1,j}$. This equality also holds for the end elements if the missing elements of the previous row (elements numbered $-1$ and $i$) are taken to be zero.

Kolya wants to know how many odd numbers there are in row $n$ of Pascal's triangle. He started drawing the triangle, but it soon stopped fitting on the sheet of paper. So Kolya decided to do this with a computer. Help him.

The input file contains the number $n$ ($0 \le n \le 2 \cdot 10^9$).

The output file must contain one number: the count of odd numbers in row $n$ of Pascal's triangle.