사진법 저울

용 비테아사르(Byteasar)가 파티를 열어 모든 손님에게 똑같은 양의 금을 나누어 주려고 한다. 금의 무게는 양팔 저울로 잰다. 그는 표준 추를 얼마든지 가지고 있으며, 추 하나의 무게는 항상 4의 거듭제곱 그램이다($1, 4, 16, 64, \dots$). 한 번 잴 때 금은 언제나 왼쪽 접시에 올려 두고, 추는 오른쪽 접시에만, 왼쪽 접시에만, 또는 양쪽 접시에 나누어 올릴 수 있다. 양쪽 접시가 평형을 이루면 올바른 계량이다.

비테아사르는 손님마다 되도록 적은 수의 추로 금을 재고 싶어 한다. 또한 파티를 즐겁게 만들기 위해 손님마다 계량 방법이 서로 달라야 한다. 어떤 거듭제곱의 추를 몇 개 쓰는지, 또는 같은 추들을 양쪽 접시에 어떻게 나누어 놓는지가 다르면 두 계량은 서로 다른 것으로 본다.

각 손님에게 주는 금의 양 $n$(그램)이 주어질 때, 가능한 한 적은 수의 추를 사용하는 서로 다른 계량의 수를 구하여라. 이 수가 매우 커질 수 있으므로 $10^9$으로 나눈 나머지를 출력한다.

다음을 수행하는 프로그램을 작성하여라.

• 표준 입력에서 금의 양 $n$을 읽는다,
• 정확히 $n$그램을 최소 개수의 추로 재는 방법의 수를 계산한다,
• 그 수를 $10^9$으로 나눈 나머지를 출력한다.

첫째 줄에 양의 정수 $n$이 하나 주어진다 $(1 \le n < 10^{1000})$. 각 손님에게 줄 금의 양(그램)이다.

$n$그램을 최소 개수의 추로 재는 서로 다른 계량의 수를 $10^9$으로 나눈 나머지를 정수 하나로 출력한다.

$166$그램을 재려면 추가 $7$개 필요하며, 다음 $3$가지 방법으로 잴 수 있다.

1. 금은 왼쪽 접시에, 추 $64, 64, 16, 16, 4, 1, 1$은 오른쪽 접시에 올린다,
2. 금과 추 $64, 16, 16$을 왼쪽 접시에, 추 $256, 4, 1, 1$을 오른쪽 접시에 올린다,
3. 금과 추 $64, 16, 4, 4, 1, 1$을 왼쪽 접시에, 추 $256$을 오른쪽 접시에 올린다.