#include <bits/stdc++.h>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int mod = 666013;
long long n;
long long a[2][2] = {{0, 1}, {1, 1}};
long long r[2][2] = {{1, 0}, {0, 1}};

static inline void prod(long long x[2][2], long long y[2][2]) {
    long long e00 = (x[0][0] * y[0][0] + x[0][1] * y[1][0]) % mod;
    long long e01 = (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % mod;
    long long e10 = (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % mod;
    long long e11 = (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % mod;

    x[0][0] = e00;
    x[0][1] = e01;
    x[1][0] = e10;
    x[1][1] = e11;
}

static inline void put(long long e) {
    while(e) {
        if(e & 1) prod(r, a);
        prod(a, a);
        e >>= 1;
    }
}

int main() {
    fin >> n;
    put(n - 1);
    fout << r[1][1];

    return 0;
}