P6065 [USACO05JAN] Sumsets S
Description
Given an integer $N$, how many ways are there to decompose $N$ into a sum of several powers of $2$?
Input Format
Input an integer $N$ ($1 \leq N \leq 10^6$).
Output Format
Output the number of valid decompositions modulo $10^9$.
Explanation/Hint
All valid decompositions are as follows.
- 1+1+1+1+1+1+1
- 1+1+1+1+1+2
- 1+1+1+2+2
- 1+1+1+4
- 1+2+2+2
- 1+2+4
Translated by ChatGPT 5