#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 1e9 + 3;
const int MOD = 666013;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int N;

struct mat
{
    int x;
    int y;
    int z;
    int t;

    mat () {
        x = 0;
        y = 0;
        z = 0;
        t = 0;
    }
};

mat multiply(mat A, mat B)
{
    mat ans;

    ans.x = ((1LL * A.x * B.x) % MOD + (1LL * A.y * B.z) % MOD) % MOD;
    ans.y = ((1LL * A.x * B.y) % MOD + (1LL * A.y * B.t) % MOD) % MOD;
    ans.z = ((1LL * A.z * B.x) % MOD + (1LL * A.t * B.z) % MOD) % MOD;
    ans.t = ((1LL * A.z * B.y) % MOD + (1LL * A.t * B.t) % MOD) % MOD;

    return ans;
}

mat FastPOW(mat base, int exp)
{
    mat ans;
    ans.x = 1;
    ans.y = 1;
    ans.z = 1;
    ans.t = 1;

    for(int i = 0; (1 << i) <= exp; ++i) {
        if((exp >> i) & 1)
            ans = multiply(ans, base);

        base = multiply(base, base);
    }
    return ans;
}

int main()
{
    fin >> N;

    mat F1;

    F1.x = 0;
    F1.y = 1;
    F1.z = 1;
    F1.t = 1;

    mat Fk = FastPOW(F1, N - 2);

    fout << Fk.t << '\n';

    return 0;
}