#include <iostream>
#include <cstdio>
using namespace std;

int n, cnt;
bool to[100000005];

void search (int t) {
    if (t > n) {
        cnt = (cnt + 1) % 1000000001;
        return;
    }
    to[t] = false;
    search(t + 1);
    if (t % 2 == 0 && to[t / 2]) return;
    if (t % 3 == 0 && to[t / 3]) return;
    to[t] = true;
    search(t + 1);
}

int main() {
    scanf("%d", &n);
    search(1);
    printf("%d\n", cnt);
    return 0;
}