#include <fstream>

using namespace std;

const int MOD= 666013;

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

int f1[2][3], f2[2][3];

void init()
{
    f1[0][0]= 0;
    f1[0][1]= 1;
    f1[1][0]= 1;
    f1[1][1]= 1;

    f2[0][0]= 1;
    f2[0][1]= 1;
    f2[1][0]= 1;
    f2[1][1]= 1;
}

void next_fib( int X )
{
    long long aux00= 0, aux01= 0, aux10= 0, aux11= 0;

    while( X>0 )
    {

        if ( X%2==1 )
        {
            aux00= ( (long long)f2[0][0] * f1[0][0] + (long long)f2[0][1] * f1[1][0] )% MOD;
            aux01= ( (long long)f2[0][0] * f1[0][1] + (long long)f2[0][1] * f1[1][1] )% MOD;
            aux10= ( (long long)f2[1][0] * f1[0][0] + (long long)f2[1][1] * f1[1][0] )% MOD;
            aux11= ( (long long)f2[1][0] * f1[0][1] + (long long)f2[1][1] * f1[1][1] )% MOD;

            f2[0][0]= aux00;
            f2[0][1]= aux01;
            f2[1][0]= aux10;
            f2[1][1]= aux11;
        }

        aux00= ( (long long)f1[0][0] * f1[0][0] + (long long)f1[0][1] * f1[1][0] ) % MOD;
        aux01= ( (long long)f1[0][0] * f1[0][1] + (long long)f1[0][1] * f1[1][1] ) % MOD;
        aux10= ( (long long)f1[1][0] * f1[0][0] + (long long)f1[1][1] * f1[1][0] ) % MOD;
        aux11= ( (long long)f1[1][0] * f1[0][1] + (long long)f1[1][1] * f1[1][1] ) % MOD;

        f1[0][0]= aux00;
        f1[0][1]= aux01;
        f1[1][0]= aux10;
        f1[1][1]= aux11;

        X/=2;
    }
}

int main(  )
{
    int K;

    in >> K;

    init();

    next_fib( K-1 );

    out << f2[0][0] << '\n';

    return 0;
}