题目描述

农民约翰命令他的奶牛搜索不同的数字集，这些数字总和等于一个给定的数字。

奶牛只使用$\red{2}$的整数幂。以下是可能的数字集，总和为$\red{7:1）}$

$\red{1+1+1+1+1+1+1+12）}$$\red{1+1+1+1+1+1+2 3）}$$\red{1+1+1+2+2 4）}$$\red{1+1+1+4 5）}$$\red{1+2+2+2 6）}$$\red{1+2+4}$

帮助$\red{FJ}$计算给定整数$\red{N（}$$\red{1<=N<=1000000）}$的所有可能表示。

给出一个$\red{N(1≤}$$\red{N≤}$$\red{10^6)，}$使用一些$\red{2}$的若干次幂的数相加来求之．问有多少种方法

输入格式

一个整数$\red{N.}$

输出格式

方法数．这个数可能很大，请输出其在十进制下的最后$\red{9}$位

样例

输入样例

7

输出样例

6