# Appreciation

/*
 * Problem :: 2410 / 2의 멱수의 합
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - dp[i][j] = i 를 만드는 2^j 이하의 2의 멱수의 합으로 나타내는 경우의 수
 *   dp[7][2] = 2 <= [1+1+1+4], [1+2+4]
 *   + for (int i=1; i<=N; i++) {
 *         for (int j=0, v=1; i-v>=0; j++, v*=2) {
 *             for (int k=0; k<=j; k++) {
 *                 dp[i][j] += dp[i-v][k];
 *                 dp[i][j] %= 1'000'000'000;
 *             }
 *         }
 *     }
 *     # 통과는 되지만 시간이 552ms 가 걸리는데
 *       다른 사람들의 풀이는 4ms 밖이 되질 않네?
 *
 * - dp[i] = i 를 2의 멱수의 합으로 나타내는 경우의 수
 *   + dp[7] 에서 각 경우의 모든 수에 2를 곱한다면
 *     dp[14] 에서 모든 수가 2 이상으로 이루어진 경우의 수가 된다!
 *   + dp[7] 에서 각 경우에 1을 더한다면
 *     dp[8] 에서 모든 경우에 적어도 하나 이상의 1 을 사용한 경우의 수가 된다!
 *     # 위를 통해 [1개 이상의 1 을 사용한 경우의 수] + [2 이상만을 사용한 경우의 수]
 *       로 나눌 수 있다!
 *       -> dp[i(짝수)] = dp[i-1] + dp[i/2]
 *          dp[i(홀수)] = dp[i-1]
 *
 * Point
 * - 잘 생각해보면 N 이 홀수인 경우에는
 *   모든 경우에 1 이 들어갈 수밖에 없다
 *   + 1 이외 2의 모든 멱수는 짝수이다
 * 
 * - 구글링의 도움을 받았다
 *   + 위와같은 풀이를 생각해낸 사람들이 정말 대단하다
 *     # 범재는 노력하는 수밖에
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;

    // Process
    int dp[N+1]; /* dp[i] = i 를 2의 멱수의 합으로 나타내는 경우의 수 */
    memset(dp, 0, sizeof(dp));
    dp[1] = 1;

    for (int i=2; i<=N; i++) {
        dp[i] += dp[i-1];
        if (i%2 == 0) { /* i 가 짝수인 경우 */
            dp[i] += dp[i/2];
            dp[i] %= 1'000'000'000;
        }
    }

    // Control : Output
    cout << dp[N] << endl;
}

// Helper Functions
/* None */