#include <fstream>
using namespace std;

ofstream out("kfib.out");

const int MOD = 666013 ;
int M[2][2] , Z[2][2];

int n ;

void mult( int A[2][2] ,int B[2][2] )
{

    int C[2][2];

    for( int i=0 ; i < 2 ; ++i )
    {
        for( int j=0; j < 2 ; ++j )
        {
            C[i][j] = 0;
                for( int k = 0 ; k < 2 ; ++k )
                {
                    C[i][j]+= 1LL *  A[i][k] * B[k][j]  % MOD;
                    if( C[i][j] >= MOD )
                        C[i][j]-=MOD;
                }
        }
    }

    for( int i=0 ; i < 2 ; ++i )
    {
        for( int j=0 ; j < 2 ; ++j )
            A[i][j] = C[i][j];
    }

}

void poww( int p , int M[2][2] )
{

    M[0][0] = 0;
    M[1][1] = 1;

    for( ; p ; p >>=1 )
    {
        if( p & 1 )
        {
            mult(M,Z);
        }

        mult(Z,Z);
    }
}


int main()
{
    ifstream in("kfib.in");

    in >> n ;

    Z[0][0] = 0;
    Z[0][1] = 1;
    Z[1][0] = 1;
    Z[1][1] = 1;

    poww( n-1 , M  );

    out << M[1][1] ;


    return 0;


}