Функція \(f(x)\), визначена для цілих невід’ємних чисел \(x\), задовольняє такі умови.

• \(f(0) = 1\).

• \(f(k)\) = \(f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)\) для будь-якого натурального \(k\).

Тут \(\lfloor A \rfloor\) позначає значення \(A\), обрізане до цілого числа.

Знайдіть \(f(N)\).

Обмеження

• \(N\) є цілим числом, яке задовольняє \(0 \le N \le 10^{18}\).

Формат вхідних даних

Вхідний потік містить ціле число \(N\)

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

2

Приклад вихідних даних

3

Маємо \(f(2)\) = \(f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor)\) = \(f(1)\) + \(f(0)\) =( \(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor))\) + \(f(0)\) =(\(f(0)+f(0)\)) + \(f(0)\)= 3

Приклад вхідних даних

0

Приклад вихідних даних

1

Приклад вхідних даних

100

Приклад вихідних даних

55