#include <bits/stdc++.h>
using namespace std;

const int p=1000000000;

int main() {
    std::vector<int> a(1000001);
    a[1]=1,a[2]=2;
    for(int i=3;i<=1000001;i++){
        if(i%2==0){
            a[i]=(a[i/2]+a[i-1])%p;
        }else a[i]=(a[i-1])%p;
    }
    int n;
    while(cin>>n){
        cout<<a[n]<<endl;
    }
}

为了防止数据过大，我们先预生成，然后直接取，保证效率一致，然后，就是这个结构的原理，对于整数的拆分，其实可以有两种做法，第一种就是完全背包问题，第二种就是利用数学特性进行解决，完全背包这里不讲了，用一个二维数组就可以模板化的得到一个等值背包问题，这里解释一下这个数学解法，首先我们分析简单的，奇数，奇数的拆分一定存在一个1，那么这个必然的1就没有了意义，整个拆分的个数就可以缩减为上一个偶数的拆分个数，然后是偶数，偶数有两种拆分，拆出来奇数1，不拆出来奇数1，这两个情况是1的拆分的完备事件组，那么我们对1进行这样的区分，然后，继续分析，假如拆出来1，就变成了奇数，且这种拆分中，1也是必然存在一个，直接收缩为上一个奇数的拆分情况即可，对于不拆出1的情况，对于一个偶数的拆分，一定是纯粹的偶数的组合，那么，偶数的组合都是2的倍数，我们提取2这个必然存在的元素，就把这个问题收缩到i/2的情况，这样，我们就得到了一个基础的递归函数，就已经可以解决这个问题了。