题目描述

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

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

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

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

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

输入格式

一个整数${N.}$

输出格式

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

样例

输入样例

7

输出样例

6