Present10

시간 제한2초메모리 제한1024 MB

요약

1로 시작하는 교대 이진 문자열이 주어질 때, 서로 다른 1로만 이루어진 이진수들의 합으로 나타내는 데 필요한 항의 개수를 구하고 불가능하면 0을 출력합니다.

난이도: 보통10점 중 7점
유형: 수학, 조합론, 정수론
정답자: 아직 제출이 없습니다

문제

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: 10102=112+1112; 10101012=1112+11112+1111112; 101010101012 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·109

예제2

예제 1
입력
```
6
```
예상 출력
```
4
```
예제 2
입력
```
5
```
예상 출력
```
0
```