正整数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