시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 36 | 25 | 17 | 65.385% |
Треугольник Паскаля --- это бесконечный треугольник из чисел, который имеет следующий вид:
1 | ||||||||||||||||
1 | 1 | |||||||||||||||
1 | 2 | 1 | ||||||||||||||
1 | 3 | 3 | 1 | |||||||||||||
1 | 4 | 6 | 4 | 1 | ||||||||||||
1 | 5 | 10 | 10 | 5 | 1 | |||||||||||
1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||||||||
1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | |||||||||
... | ... | ... | ... | ... | ... | ... | ... | ... |
Строки треугольника Паскаля нумеруются с нуля, числа в каждой строке также нумеруются с нуля. Нулевая строка содержит единственное число --- единицу, а каждая следующая содержит на одно число больше, чем предыдущая. Нулевое и последнее число в каждой строке равны единице, а каждое из остальных равно сумме двух чисел предыдущей строки, расположенных над ним.
Таким образом, $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$-ой строке треугольника Паскаля.
0
1
5
4
7
8