题目描述

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

2 的次幂形式为 $2^k$：有 $1, 2, 4, 8, 16, 32, 64, 128, \dots$

输入格式

输入一个整数 $N$ ($1 \le N \le 10^9$)。

输出格式

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

输入数据 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$

数据范围

• 对于 30% 的数据，$N \le 30$
• 对于 60% 的数据，$N \le 100$
• 对于 100% 的数据，$N \le 10^6$