填空题

统计累加算式

Question

一个正整数可以表示为多个正整数相加的表达式，表达式中的各个正整数要求都是2的幂。例如给定正整数7，它有下列六个符合要求的表达式：

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

因此，正整数7符合条件的表达式个数是6. 编写一个程序，对于给定的正整数N(1 <= N <= 1,000)，输出符合条件的表达式个数。要求：时间复杂度不高于O(N)。

输入描述： 一个整数（>=1并且<=1000）输入样例： 7 输出描述： 表达式个数输出样例 6