Лето 9

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

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

Таким образом, `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\ ≤\ n\ ≤\ 2⋅10^9`).

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

0

1

5

4

7

8