E. Функция

Функция $f$ с целыми неотрицательными аргументами определена так:

• $f(0) = 0$;
• $f(1) = 1$;
• $f(2n) = f(n)$;
• $f(2n+1) = f(n) + f(n+1)$.

Вычислите $f(n)$.

Посмотрите, какие аргументы встречаются в вызовах: их гораздо меньше, чем самих вызовов. При $n = 10^{12}$ различных аргументов всего 66, а вызовов без запоминания в худшем случае — 535 828 590, почти секунда работы. Запас есть, но нулевой: стоит границе подрасти, и решение без запоминания перестанет проходить. В домашней задаче это ровно так и происходит.

Одна строка содержит число $n$ ($0 \le n \le 10^{12}$).

Одно число — $f(n)$.