P6065 [USACO05JAN] Sumsets S
题目描述
给出一个整数 $N$，将 $N$ 分解为若干个 $2$ 的次幂的和，共有多少种方法？
输入格式
输入一个整数 $N$（$1 \leq N \leq 10^6$）。
输出格式
输出方案数对 $10^9$ 取模的结果。
说明/提示
所有合法方案如下：
- 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