#include <cstdio>

#define MOD 666013

using namespace std;

FILE *f, *g;

int k;

int m[5][5];
int cm[5][5];
int c[5][5];

void readFile()
{
    f = fopen("kfib.in", "r");

    fscanf(f, "%d", &k);

    fclose(f);
}

int ok;

void inmMatrix(int a[][5], int b[][5], int cod)
{
    int i, j;

    if(cod == 1 && ok == 0)
    {
        ok = 1;
        for(i = 1; i <= 2; i ++)
        {
            for(j = 1; j <= 2; j ++)
                a[i][j] = b[i][j];
        }
    }

    else
    {
        for(i = 1; i <= 2; i ++)
        {
            for(j = 1; j <= 2; j ++)
            {
                c[i][j] = 1LL * a[i][1] * b[1][j] % MOD + 1LL * a[i][2] * b[2][j] % MOD;
                c[i][j] %= MOD;
            }
        }

        for(i = 1; i <= 2; i ++)
        {
            for(j = 1 ; j <= 2; j ++)
            {
                a[i][j] = c[i][j];
            }
        }
    }
}

void putere(int b)
{
    int i;

    for(i = 0; (1 << i) <= b; i ++)
    {
        if(((1 << i) & b) != 0)
        {
            inmMatrix(m, cm, 1);
        }

        inmMatrix(cm, cm, 2);
    }
}

int rez;

void solve()
{
    cm[1][1] = cm[1][2] = cm[2][1] = 1;

    putere(k - 1);

    rez = m[1][1];
}

void printFile()
{
    g = fopen("kfib.out", "w");

    fprintf(g, "%d\n", rez);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}