You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

2的次幂形式为 $2^x$：有1,2,4,8,16,32,64,128,......

输入格式

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

输出格式

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

7

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

数据范围

30% $n \le 30$

60% $n \le 100$

100% $n \le 10^6$