#include <fstream>

using namespace std;

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

const int MOD = 666013;

int N;

int mat[3][3], aux[3][3], init[3][3];

void Quick_exp( int pow )
{
    if( pow <= 1 ) return;

    Quick_exp( pow / 2 );

    for( int i = 1; i <= 2; ++i )
        for( int j = 1; j <= 2; ++j )
        {
            aux[i][j] = 0;
            for( int J = 1, I = 1; J <= 2; ++J, ++I )
                aux[i][j] += ( 1LL * mat[i][J] * mat[I][j] ) % MOD;

            aux[i][j] %= MOD;
        }

    if( pow % 2 )
    {
        for( int i = 1; i <= 2; ++i )
            for( int j = 1; j <= 2; ++j )
                mat[i][j] = aux[i][j];

        for( int i = 1; i <= 2; ++i )
            for( int j = 1; j <= 2; ++j )
            {
                aux[i][j] = 0;
                for( int J = 1, I = 1; J <= 2; ++J, ++I )
                    aux[i][j] += ( 1LL * mat[i][J] * init[I][j] ) % MOD;

                aux[i][j] %= MOD;
            }
    }

    for( int i = 1; i <= 2; ++i )
        for( int j = 1; j <= 2; ++j )
            mat[i][j] = aux[i][j];
}

int main()
{
    fin >> N;

    init[1][2] = 1;
    init[2][1] = 1;
    init[2][2] = 1;

    for( int i = 1; i <= 2; ++i )
        for( int j = 1; j <= 2; ++j )
            mat[i][j] = init[i][j];

    Quick_exp( N - 2 );

    /*for( int i = 1; i <= 2; ++i )
    {
    for( int j = 1; j <= 2; ++j )
    fout << mat[i][j] << ' ';

    fout << '\n';
    }*/

    fout << ( 1LL * mat[1][2] + mat[2][2] ) % MOD << '\n';

    fout.close();

    return 0;
}