시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1155 462 336 39.437%

문제

어떤 자연수 N을 2의 멱수의 합으로 나타내는 경우의 수를 구하는 프로그램을 작성하시오. 2의 멱수라는 것은, 2^k으로 표현되는 자연수를 의미한다.

예를 들어 7을 2의 멱수의 합으로 나타내는 경우의 수는 다음의 여섯 가지가 있다.

  1. 1+1+1+1+1+1+1
  2. 1+1+1+1+1+2
  3. 1+1+1+2+2
  4. 1+1+1+4
  5. 1+2+2+2
  6. 1+2+4

입력

첫째 줄에 N(1≤N≤1,000,000)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력

7

예제 출력

6

힌트