Треугольник Паскаля

Треугольник Паскаля --- это бесконечный треугольник из чисел, который имеет следующий вид:

Строки треугольника Паскаля нумеруются с нуля, числа в каждой строке также нумеруются с нуля. Нулевая строка содержит единственное число --- единицу, а каждая следующая содержит на одно число больше, чем предыдущая. Нулевое и последнее число в каждой строке равны единице, а каждое из остальных равно сумме двух чисел предыдущей строки, расположенных над ним.

Таким образом, $i$-ая строка содержит $i + 1$ число.  Если обозначить $j$-ый элемент $i$-ой строки как $a\_{i,j}$, то выполняется равенство $a\_{i,j} = a\_{i - 1,j - 1} + a\_{i-1,j}$. Заметим, что это равенство выполняется и для крайних элементов, если положить отсутствующие элементы предыдущей строки (элементы с номерами $-1$ и $i$) равными нулю.

Коля хочет узнать, сколько нечетных чисел в $n$-ой строке треугольника Паскаля. Он начал рисовать треугольник, но очень скоро тот перестал помещаться на листочек. Тогда Коля решил сделать это с помощью компьютера. Помогите ему.

Во входном файле содержится число $n$ ($0 \le n \le 2 \cdot 10^9$).

Выходной файл должен содержать одно число --- количество нечетных чисел в $n$-ой строке треугольника Паскаля.