#include <iostream>
#include <vector>
#include <fstream>

#define ll long long

using namespace std;

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

const int MOD = 666013;

int k;

struct matr
{
    ll m[2][2];
};

matr matmult(matr& M1, matr& M2)
{
    matr res = { 0, 0, 0, 0 };
    for( int i = 0; i < 2; ++i )
        for( int j = 0; j < 2; ++j )
        {
            for( int t = 0; t < 2; ++t )
            {
                res.m[i][j] += M1.m[t][j] * M2.m[i][t];
                res.m[i][j] %= MOD;
            }
        }
    return res;
}

matr matrpow(matr M, int k)
{
    matr res = {1, 0, 0, 1};///?
    while(k)
    {
        if(k % 2)
            res = matmult(res, M);
        k /= 2;
        M = matmult(M, M);
    }

    return res;
}

int main()
{
    fin >> k;

    if(k == 0)
        fout << 0 << "\n";
    else if(k == 1)
        fout << 1 << "\n";
    else
    {
        matr M = {1, 1, 1, 0};

        M = matrpow(M, k);

        fout << M.m[0][1] << "\n";
    }

    return 0;
}