Numbers and Numerals
How many discoveries can be made by exploring numbers and the digits they consist of!
Petryk loves arithmetic, and beyond his homework, he constantly invents additional problems. One day, he began adding the sum of its digits to natural numbers. Petryk discovered that some numbers, like 20, cannot be obtained from other numbers through such operations. He didn't like these numbers and called them ugly.
Later, when Petryk started studying computer science, he conducted similar research with natural numbers in the binary numeral system. For example, the binary number 1110_2 (which is 14 in the decimal system) can be obtained from the number 1100_2 (which is 12 in the decimal system) by adding the sum of its digits:
1100_2 + 10_2 = 1110_2.
Petryk decided to explore the set of binary ugly numbers. He found the first five ugly numbers without difficulty: 1 = 1_2, 4 = 100_2, 6 = 110_2, 13 = 1101_2, 15 = 1111_2. He plans to continue his work with the help of a computer.
Your task is to write a program that determines the number of binary ugly numbers that do not exceed a given number n.
Input
The first line of the input file contains the number n, written in the decimal numeral system (1 ≤ n ≤ 10^18).
Output
The single line of the output file should contain a single number — the number of binary ugly numbers that do not exceed n.