Sum of Powers of Two
Time limit2sMemory limit128 MB
Count the ways to write N as an unordered sum of powers of two, modulo one billion.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Math, Combinatorics
- Solved
- No attempts yet
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.