#include <fstream>

using namespace std;

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

struct matrice
{
    long long m[3][3];
};

matrice A, B;
long long n;

matrice ridicare_la_putere_matrice ( matrice A, int nr );
matrice inmultire_matrici ( matrice A, matrice B );

int main()
{
    fin >> n;

    A.m[1][1] = A.m[1][2] = A.m[2][1] = 1;
    A.m[2][2] = 0;

    B.m[1][1] = B.m[2][1] = 1;
    B.m[1][2] = B.m[2][2] = 0;

    A = ridicare_la_putere_matrice ( A, n - 2 );
    B = inmultire_matrici ( A, B );

    fout << B.m[1][1];

    return 0;
}

matrice ridicare_la_putere_matrice ( matrice A, int nr )
{
    if ( nr == 0 );
    else if ( nr == 1 ) return A;
    else if ( nr % 2 == 0 ) A = ridicare_la_putere_matrice ( inmultire_matrici ( A, A ), nr / 2 );
    else A = inmultire_matrici ( A, ridicare_la_putere_matrice ( inmultire_matrici ( A, A ), nr / 2 ) );

    return A;
}

matrice inmultire_matrici ( matrice A, matrice B )
{
    matrice rezultat;

    rezultat.m[1][1] = ( ( A.m[1][1] * B.m[1][1] ) % 666013 + ( A.m[1][2] * B.m[2][1] ) % 666013 ) % 666013;
    rezultat.m[1][2] = ( ( A.m[1][1] * B.m[1][2] ) % 666013 + ( A.m[1][2] * B.m[2][2] ) % 666013 ) % 666013;
    rezultat.m[2][1] = ( ( A.m[2][1] * B.m[1][1] ) % 666013 + ( A.m[2][2] * B.m[2][1] ) % 666013 ) % 666013;
    rezultat.m[2][2] = ( ( A.m[2][1] * B.m[1][2] ) % 666013 + ( A.m[2][2] * B.m[2][2] ) % 666013 ) % 666013;

    return rezultat;
}