P1087
时间限制: 0 s
内存限制: 128 MB
提交：6
正确：3
分值：99
题目描述
正整数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。
输出
一个整数，表示不同方案的数量。
样例
提示
1 < = N < = 1000000