E. Функция на больших числах

Та же функция: $f(0) = 0$, $f(1) = 1$, $f(2n) = f(n)$, $f(2n+1) = f(n) + f(n+1)$.

Граница выросла до $10^{18}$. Приём тот же, но теперь надо проследить, что ни аргумент, ни ответ не переполняют тип.

Ответ помещается в 64-битный тип: при $n \le 10^{18}$ наибольшее значение $f$ равно 2 504 730 781 961 и достигается на $n = 960\,767\,920\,505\,705\,813$.

Здесь запоминание уже обязательно. Без него на этом самом числе рекурсия не заканчивается за разумное время, а с ним различных аргументов ровно 100.

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

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