【tyvj1087】sumsets

2014年1月23日1,1200

题目描述

        正整数N可以被表示成若干2的幂次之和。例如,N  =  7时,共有下列6种不同的方案: 1)  1+1+1+1+1+1+1 2)  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         给出正整数N,计算不同方案的数量(保留最后9位数字)。

输入

一个整数,表示正整数N。

输出

一个整数,表示不同方案的数量。

样例输入

7

样例输出

6

提示

 

1  < =  N  < =  1000000

 

代码