2의 멱수의 합
시간 제한2초메모리 제한128 MB
N을 순서를 구분하지 않는 2의 거듭제곱들의 합으로 나타내는 방법의 수를 10억으로 나눈 나머지로 구하는 문제입니다.
문제
자연수 N을 2의 멱수들의 합으로 나타내는 방법의 수를 구하시오. 2의 멱수는 2^k 꼴로 표현되는 자연수이다.
같은 항들의 순서만 다른 표현은 하나로 센다.
입력
첫째 줄에 자연수 N이 주어진다.
1 <= N <= 1,000,000
출력
첫째 줄에 N을 2의 멱수들의 합으로 나타내는 방법의 수를 출력한다.
답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.