正整數(shù)N可以被表示成若干2的冪次之和。例如，N  =  7時(shí)，共有下列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         

給出正整數(shù)N，計(jì)算不同方案的數(shù)量（保留最后9位數(shù)字）。

7

6