/* Ridicam matricea Z : 0 1
                        1 1

                    la puterea K - 1 in timp logaritmic
    Apoi vom face fix * Z
    Ridicarea la putere a unei matrice in timp logaritmic : descompunem puterea la care trebuie
    ridicata matricea in baza 2. Parcurgem cifrele (de la coada la cap) : automat inmultim matricea
    cu ea insasi (Z * Z), iar daca cifra curenta din descopunere este 1 o inmultim cu varianta ei initiala (copie_z).

    La inceput vom initializa matricea cu matricea unuitate (Z[i][i] = 1 adica umplem diagonala principala de 1).
    Spor !
*/

#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, lg;

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;

    aux = K - 1;
    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);
        }
    }

    inmultire(fix, z);

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

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