Sum of Powers of Two

Time limit

Memory limit

128 MB

Problem

Given a positive integer N, count the number of ways to write N as a sum of powers of two. A power of two is a positive integer of the form 2^k.

Representations that differ only in the order of their terms are counted as the same representation.

Input

The first line contains a positive integer N.

1 <= N <= 1,000,000

Output

Print the number of ways to write N as a sum of powers of two.

Because the answer can be large, print it modulo 1,000,000,000.