[USACO05JAN] Sumsets S

题目描述

给出一个整数 $N$，将 $N$ 分解为若干个 $2$ 的次幂的和，共有多少种方法？

输入格式

输入一个整数 $N$（$1 \leq N \leq 10^6$）。

输出格式

输出方案数对 $10^9$ 取模的结果。

样例 #1

样例输入 #1

7

样例输出 #1

6

提示

所有合法方案如下：

• 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