04. Prokopij - 2

Приказчик Прокопий вёл учёт в лавке купца Пятипузова. Считал Прокопий отлично, а вот записывать числа ему было непросто: после Гангутского сражения (Прокопий-то моряком раньше был), мог он обрубком правой руки писать только нолики и единички. Про двоичную систему Прокопий не знал, но придумал собственный способ записи чисел. Представлял он число в виде суммы чисел, состоящих только из единиц и нулей. К примеру, число 1714 (год того самого сражения при Гангуте) он иногда представлял как 1111 + 101 + 101 + 101 + 100 + 100 + 100, а иногда как 1101 + 111 + 101 + 101 + 100 + 100 + 100, но всегда слагаемых было минимальное возможное количество и шли они в порядке невозрастания. Плюсиков Прокопий, естественно, не писал, оставлял вместо них пробелы.

Разработайте программу, которая получает на вход натуральное число N и подсчитывает количество способов представить его в системе Прокопия. Напомним: Прокопий представлял число как сумму.

Входные данные. Натуральное число, не превышающее 99999.

Выходные данные. натуральное число – количество способов представления введённого числа в системе Прокопия.

Для отправки решений необходимо выполнить вход.