2의 멱수의 합

자연수 N을 2의 멱수들의 합으로 나타내는 방법의 수를 구하시오. 2의 멱수는 2^k 꼴로 표현되는 자연수이다.

같은 항들의 순서만 다른 표현은 하나로 센다.

첫째 줄에 자연수 N이 주어진다.

1 <= N <= 1,000,000

첫째 줄에 N을 2의 멱수들의 합으로 나타내는 방법의 수를 출력한다.

답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.