#include <fstream>
#include <cstring>

using namespace std;

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

const int MOD = 666013;
const int DIM = 5;

int K;

struct matrix
{
    int N, M;
    long long a[DIM][DIM];

    matrix()
    {
        N = M = 0;
        memset(a, 0, sizeof(a));
    }

    matrix operator * (const matrix other)
    {
        matrix rez;

        rez.N = N;
        rez.M = other.M;

        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= other.M; j++)
                for(int c = 1; c <= M; c++)
                    rez.a[i][j] = rez.a[i][j] + a[i][c] * other.a[c][j];

        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= M; j++)
                rez.a[i][j] %= MOD;

        return rez;
    }
};

matrix RidPut(int exp)
{
    matrix sol, aux;

    sol.N = sol.M = 2;
    sol.a[1][1] = sol.a[2][2] = 1;

    aux.N = aux.M = 2;
    aux.a[1][1] = 0;
    aux.a[1][2] = aux.a[2][1] = aux.a[2][2] = 1;

    for(int i = 1; i <= exp; i <<= 1)
        {
            if(i & exp)
                sol = sol * aux;

            aux = aux * aux;
        }

    return sol;
}

int main()
{
    fin >> K;

    matrix z = RidPut(K);

    matrix m;
    m.N = 1, m.M = 2;
    m.a[1][1] = 0, m.a[1][2] = 1;

    matrix p = m * z;

    fout << p.a[1][1];

    return 0;
}