Problem 22056 --2的幂数

22056: 2的幂数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 8  Solved: 5
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][84kb]

Description

 

小明开始学习二进制转化到十进制,其中要用到2的幂(23次幂就是32相乘),他觉得这个很有意思。既然通过2的幂相加可以得到十位数,那么反过来,一个十进制数是否可以通过若干个2的幂相加得到呢?

小明开始研究起来,他先列出了所有2的幂:1,2,4,8,16,32,64……。

4=1+1+1+1

4=1+1+2

4=2+2

4=4                 4共有4种方法

7=1+1+1+1+1+1+1

7=1+1+1+1+1+2

7= 1+1+1+2+2

7=1+1+1+4

7=1+2+2+2

7= 1+2+4       

共有6种方法。1+2+42+1+4认为是同一个等式,因为它们的组成相同。

现在小明想要知道,给出一个十进制数,可以写出多少种,用若干个2的幂数相加的式子。

Input

 

输入文件名为power.in

第一行包含1个正整数n 1<=n<=1000

Output

 

输出文件power.out1行,n能用2的幂数相加的不同式子的种数。

Sample Input

7

Sample Output

6

HINT

 


【数据范围】



50%的数据1<=n<=20



100%的数据1<=n <=1000

Source

[Submit][Status]