题目描述

给出一个整数 $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