#include <bits/stdc++.h>

#define llg long long

#define MOD 666013
#define LOGN    35

llg N;

llg A[2][2], Unit[2][2] = {{1, 0}, {0, 1}}, Null[2][2];
llg t_rez, Rez[2][2][2];
llg POW2[LOGN][2][2];

void Atrib(llg A[2][2], llg B[2][2]) {
    for (llg i=0, j; i<2; ++i)
        for (j=0; j<2; ++j)
            A[i][j] = B[i][j];
}

void Multiply(llg A[2][2], llg B[2][2], llg C[2][2]) {
    Atrib(A, Null);
    for (llg i=0, j, k; i<2; ++i)
        for (j=0; j<2; ++j)
            for (k=0; k<2; ++k)
                A[i][j] += B[i][k] * C[k][j] % MOD,
                A[i][j] %= MOD;
}

void FastPow(llg Exp) {
    Atrib(POW2[0], A);
    for (llg i=1; i<LOGN; ++i)
        Multiply(POW2[i], POW2[i-1], POW2[i-1]);

    t_rez = 1;
    Atrib(Rez[0], Unit);
    llg p = 0;
    while (Exp) {
        if (Exp&1)
            Multiply(Rez[t_rez], Rez[1-t_rez], POW2[p]), t_rez = 1-t_rez;
        p ++;
        Exp/=2;
    }   t_rez = 1-t_rez;
}

std::ifstream In ("kfib.in");
std::ofstream Out("kfib.out");

void Citire() {
    In >> N;
}

void Rezolvare() {
    A[0][0] = A[0][1] = A[1][0] = 1;
    FastPow(N-2);
    Out << (Rez[t_rez][0][0] + Rez[t_rez][0][1]) % MOD << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}