考虑最后有没1.

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

long long d[1000010];

int main() {
    int N;
    cin >> N;
    
    memset(d, 0, sizeof(d));
    d[0] = 1;
    for (int i = 1; i <= N; ++i) {
        if ((i & 1) == 1) {
            d[i] = d[i - 1];
        }
        else {
            d[i] = (d[i - 1] + d[i / 2])  % 1000000000;
        }
    }
    cout << d[N] << endl;
}