#include <fstream>

using namespace std;

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

int K;
const int MOD = 666013;

struct Matrix
{
    int N, M;
    int a[5][5];

    Matrix()
    {
        N = M = 0;

        for(int i = 0; i < 5; i++)
            for(int j = 0; j < 5; j++)
                a[i][j] = 0;
    }

    Matrix operator * (const Matrix other) const
    {
        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] + 1LL * a[i][c] * other.a[c][j]) % MOD;

        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;
}