时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：2720

解决：1099

<dl> <dt> 题目描述： </dt> <dd>

一个整数总可以拆分为2的幂的和，例如：
7=1+2+4
7=1+2+2+2
7=1+1+1+4
7=1+1+1+2+2
7=1+1+1+1+1+2
7=1+1+1+1+1+1+1
总共有六种不同的拆分方式。
再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。
用f(n)表示n的不同拆分的种数，例如f(7)=6.
要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。

</dd> </dl> <dl> <dt> 输入： </dt> <dd>

每组输入包括一个整数：N(1<=N<=1000000)。

</dd> </dl> <dl> <dt> 输出： </dt> <dd>

对于每组数据，输出f(n)%1000000000。

</dd> </dl> <dl> <dt> 样例输入： </dt> <dd> 
7
</dd> </dl> <dl> <dt> 样例输出： </dt> <dd> 
6
</dd> </dl>

当n为奇数的时候，可以将其看成是其上一个偶数加上一个2的0次方，故  f（n） = f（n-1）。

当n为偶数的时候，又可以以一划分，对于含有1的情况：与n-1对应。对于没有1的情况：可以看成是n/2乘以2。所以：f（n） = f（n-1）+f（n/2）。

//Asimple
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <limits.h>
#define INF 0x7fffffff
#define mod 1000000000 
using namespace std;
const int maxn = 1000000+5;
typedef long long ll;
int n;
int a[maxn];

void init(){
    a[0] = 0;
    a[1] = 1;
    a[2] = 2;
    for(int i=3; i<maxn; i++){
        if( i % 2 ){
            a[i] = a[i-1];
        } else {
            a[i] = (a[i-1] + a[i/2])%mod;
        }
    }
    return ;
}
 
int main(){
    init();
    while( ~scanf("%d",&n) ){
        printf("%d\n",a[n]);
    }
    return 0;
}