#include <fstream>
#include <cstring>
#define infile "kfib.in"
#define outfile "kfib.out"
#define MOD 666013

using namespace std;

ifstream f(infile);
ofstream g(outfile);

int n, m[3][3], sol[3][3];

void mult(int a[][3], int b[][3], int c[][3])
{
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            for (int k = 0; k < 2; ++k)
            {
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
            }
        }
    }
}

void pow(int p, int mat[][3])
{
    int c[3][3], aux[3][3];

    memcpy(c, m, sizeof(m));
    mat[0][0] = mat[1][1] = 1;

    for (int i = 0; (1 << i) <= p; ++i)
    {
        if (p & (1 << i))
        {
            memset(aux, 0, sizeof(aux));
            mult(mat, c, aux);
            memcpy(mat, aux, sizeof(aux));
        }

        memset(aux, 0, sizeof(aux));
        mult(c, c, aux);
        memcpy(c, aux, sizeof(c));
    }
}

inline void reset()
{
    m[0][0] = 0;
    m[0][1] = 1;
    m[1][0] = 1;
    m[1][1] = 1;
}

int main()
{
    f >> n;
    reset();
    pow(n - 1, sol);
    g << sol[1][1] << '\n';
    return 0;
}