24280번 - Present10 서브태스크다국어

Let us consider a sequence of alternatively changing zeroes and ones, starting with one. This sequence can be seen as a binary representation of a positive integer. We want to present it as a sum of different binary numbers, composed only of ones (i.e. 1, 11, 111 and etc). For some sequences such presentation is possible, for others not.

For example: 1010₂=11₂+111₂; 1010101₂=111₂+1111₂+111111₂; 10101010101₂ cannot be presented as desired.

Write a program to find for a given sequence of zeros and ones the number of summands in one presentation as a sum of different binary numbers, composed only of ones, or determines that there is no such presentation.

The first line of the standard input contains only one positive integer n – the length of the considered sequence.

The only line of the standard output should only contain one non-negative integer: the number of different summands of the desired presentation or 0, if there is no such presentation.

If there is more than one possible solution, output the number of summands in any of them.

• 1 ≤ n ≤ 2·10⁹