Description

要求找出具有以下性质数的个数（包括输入的自然数 $n$ ）。先输入一个自然数 $n$ ($n \le 1000$),然后对此自然数按照如下方法进行处理：

1）不做任何处理；

2）在它的左边加上一个自然数，但该自然数不能超过原数的一半；

3）加上数后，继续按此规则进行处理，指导不能再加自然数为止。

Input Format

输入格式：一个自然数 $n$

Output Format

输出格式：输出数的个数

Sample

样例输入

6

样例输出

6

（6 16 26 126 36 136）

Hint

分析：如果用简单的模拟算法，可以得到满分，但是运算量 大，编程复杂。

如若，设$F_i$为初始值i时的满足条件总数。因为在$i$前可加入$1 – \frac{i}{2}$, 所以可以得到一个递推关系式：$F_i = F_1 + F_2 + \cdots + F_\frac{i}{2}+1$, $F_1 = 1$,这样就能够利用递推策略解题，进一步分析当i为奇数时，$F_i = F_i-1$,当i为偶数时，$F_i = F_i-1 + F_\frac{i}{2}$,这样就只需要$n$次运算就可以得到答案。