#include <bits/stdc++.h>

using namespace std;

struct Matrice
{
    int v[2][2];

    Matrice(int _00, int _01, int _10, int _11)
    {
        v[0][0] = _00;  v[0][1] = _01;
        v[1][0] = _10;  v[1][1] = _11;
    }

    friend Matrice operator * (Matrice const& A, Matrice const& B)
    {
        Matrice ans(0, 0, 0, 0);

        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < 2; ++j)
                for(int k = 0; k < 2; ++k)
                    ans.v[i][j] = (ans.v[i][j] + (1LL * B.v[i][k] * A.v[k][j]) % 666013) % 666013;

        return ans;
    }

    Matrice operator ^ (int K)
    {
        Matrice X(0, 1, 1, 1);

        if(K == 0)
            return Matrice(1, 0, 1, 0);

        if(K == 1)
            return X;

        X = (X ^ (K/2));
        X = X * X;

        if(K % 2 == 1) X = X * Matrice(0, 1, 1, 1);

        return X;
    }

};
int main()
{
    ifstream fin{"kfib.in"};
    ofstream fout{"kfib.out"};

    int K;

    fin >> K;

    Matrice M(0, 1, 1, 1);

    M = M ^ (K - 1);

    if(K == 0) fout << 0;
    else if(K == 1) fout << 1;
    else fout << M.v[1][1];

}