#include <stdio.h>
using namespace std;

#define MOD 666013

long long  m[2][3], c[3][3], fix[2][3];
long long z[3][3], copie_z[3][3];
int baza[1001];
long long K;
int  i, j, k, aux;
int p, l, lg;

void afisare (int mat[3][3])
{
    for (i=1; i<=2; ++i)
    {
        for (j=1; j<=2; ++j)
            printf ("%d ", mat[i][j]);
        printf ("\n");
    }
    printf ("\n\n\n\n\n");
}

void inmultire (long long t[3][3], long long b[3][3])
{
    for (i=1; i<=1; ++i)
        for (j=1; j<=2; ++j)
            for (k=1; k<=2; ++k)
                c[i][k] += (t[i][j] * b[j][k]) % MOD;
    for (i=1; i<=1; ++i)
        for (j=1; j<=2; ++j)
        {
            t[i][j] = c[i][j];
            c[i][j] = 0;
        }
}

void ridica_z (long long t[3][3], long long b[3][3])
{
    for (i=1; i<=2; ++i)
        for (j=1; j<=2; ++j)
            for (k=1; k<=2; ++k)
                c[i][k] += (t[i][j] * b[j][k]) %MOD;
    for (i=1; i<=2; ++i)
        for (j=1; j<=2; ++j)
        {
            t[i][j] = c[i][j];
            c[i][j] = 0;
        }
}

int main ()
{
    FILE *f = fopen ("kfib.in","r");
    FILE *g = fopen ("kfib.out","w");
    fscanf (f,"%lld", &K);

    copie_z[1][1] =  0;
    copie_z[1][2] = copie_z[2][1] = copie_z[2][2] = 1;
    z[1][1] = 1;
    z[2][2] = 1;

    fix[1][1] = 0;
    fix[1][2] = 1;

    for (l=K; l<=K; ++l)
    {
        aux = l - 1;
        lg = 0;
        while (aux)
        {
            lg ++;
            baza[lg] = aux % 2;
            aux /= 2;
        }
        for (p=lg; p>=1; --p)
        {
            ridica_z(z, z);
            if (baza[p])
            {
                ridica_z(z, copie_z);
            }
        }
        fix[1][1] = 0;
        fix[1][2] = 1;
        inmultire(fix, z);

        z[1][1] = 1;
        z[1][2] = 0;
        z[2][1] = 0;
        z[2][2] = 1;
    }

    fprintf (g,"%lld",fix[1][2]);

    fclose(g);
    fclose(f);
    return 0;
}