2063: TYVJ 1087 sumsets
内存限制:128 MB
时间限制:0.000 S
评测方式:文本比较
命题人:
提交:26
解决:13
题目描述
        正整数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