Сегодня Егор в школе проходил системы счисления, ему дали следующее определение представление числа в системе счисления:

Представлением целого положительного числа $$$n$$$ в $$$k$$$-ичной системе счисления ($$$k \ge 2$$$) называется последовательность целых неотрицательных чисел $$$a_1$$$, ..., $$$a_s$$$ такая, что $$$a_i \le k - 1$$$ для всех $$$i = 1...s$$$ и $$$a_1 \ne 0$$$, а также $$$a_s + a_{s - 1} \cdot k + a_{s - 2} \cdot k^2 + ... + a_1 \cdot k^{s - 1} = n$$$.

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

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

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

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

Решения, работающие корректно при $$$n \le 10^6$$$, будут оцениваться в 30 баллов.

Решения, работающие корректно при $$$n \le 10^{12}$$$, будут оцениваться в 60 баллов.