---

#include<iostream>
using namespace std;
int dp[1000001];
int main(){
    int n;
    dp[0]=1;
    while(cin>>n){
        for(int i=1;i<=n;i++){
            if(i%2==0){
                dp[i]=(dp[i-1]+dp[i/2])%1000000000;
            }else{
                dp[i]=dp[i-1]%1000000000;
            }
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}

每一个数都可以拆成2的次幂的形式，2的次幂有（1，2，4，6，8...），其中只包括一个奇数，那就是1。

假设给定一个数N：
1.N是奇数，那么N拆分的时候必定有一个1，因为2的次幂除了1都是偶数，由很多偶数不可能构成奇数。
所以 f(N)=f(N-1)
举例：
5=（1+4）=（1+2+2）=（1+1+1+2）=（1+1+1+1+1） ;一共有四种拆分形式
4=（4） =（2+2） =（1+1+2） = (1+1+1+1) ;一共四种拆分方式

---

2.N是偶数，那么可以分成两种情况：
2.1 N中拆分出1，N中拆分出1和上边N是奇数的情况一样，即f(N-1)
举例：
4=（4）=（2+2）=（1+1+2）=（1+1+1+1）
3=（1+2）=（1+1+1）
2.2 N中不拆分出1
不拆分出1，即都是偶数，偶数的性质可知，偶数都可以整除2，假如N的和为2m，那么除2之后变成m，但是并不影响f(N)。
举例：
4=（4）=（2+2） 都不包含1

同理，由2.1和2.2两种情况的结果相加得到完整的4的拆分。
也就是说N为偶数的情况就是f(N)=f(N-1)+f(N/2)---------------好看一点儿就是：f(2m)=f(2m-1)+f(m);