lenaivashenko16

18.02.2023 05:36 •  Информатика

Сегодня Егор в школе проходил системы счисления, ему дали следующее определение представление числа в системе счисления: Представлением целого положительного числа n в k-ичной системе счисления (k ≥ 2) называется последовательность целых неотрицательных чисел a1, ..., as такая, что ai ≤ k - 1 для всех i = 1...s и a1 ≠ 0, а также as + as - 1 · k + as - 2 · k2 + ... + a1 · ks - 1 = n.

Например, представлением числа 6 в двоичной системе счисления является последовательность 1, 1, 0, т.к. 0 + 1 · 2 + 1 · 4 = 6, а представлением числа 120 в одиннадцатиричной системе счисления является последовательность 10, 10, т.к. 10 + 10 · 11 = 120.

Можно показать, что любое целое положительное число n представимо единственным образом в k-ичной системе счисления для любого k ≥ 2.

Егор считает красивыми последовательности, которые заканчиваются ровно на два нуля. Сегодня в учебнике он наткнулся на целое положительное число n, и он захотел получить из него как можно больше красивых последовательностей, переводя n в различные системы счисления. Ему стало интересно, сколько различных красивых последовательностей он сможет получить?

Однако, так как число n очень большое, без программирования ему не обойтись. К сожалению, программировать он не умеет, поэтому обратился за к вам. Напишите программу, которая по заданному n считает количество различных красивых последовательностей, которые из него можно получить.

Формат входных данных
В единственной строке входных данных находится единственное целое число n (1 ≤ n ≤ 10^18) – число, которое увидел Егор, идя из школы.

Формат результата
Выведите единственное число – ответ на задачу.

Примеры
Входные данные
8
Результат работы
0
Входные данные
12
Результат работы
1
Входные данные
100
Результат работы
3