sumsets

        正整数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位数字）。

7

6