Функция f(n) с натуральными аргументами и значениями определена так:
f(0) = 0
f(1) = 1
f(2n) = f(n)
f(2n + 1) = f(n) + f(n + 1)
Составить программу вычисления f(n) по заданному n.
Входные данные
Дано одно число n (1 <= n <= 1018).
Выходные данные
Выведите
f(n).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
10 |
3 |
Запрещенные операторы: for; while; until