#include <iostream>
#include <fstream>

using namespace std;

const int mod = 666013;

class Matrix
{
    public:

    int N;
    int **a;

    Matrix( const int n = 0 )
    {
        N = n;
        a = new int*[N + 1];

        for ( int i = 0; i < N; ++i )
                a[i] = new int[N + 1];

        for ( int i = 0; i < N; ++i )
                for ( int j = 0; j < N; ++j )
                        a[i][j] = 0;
    }

    void reset()
    {
        for ( int i = 0; i < N; ++i )
                for ( int j = 0; j < N; ++j )
                        a[i][j] = 0;
    }

    void set( int i, int j, int val )
    {
        a[i][j] = val;
    }

    inline int print( int i, int j )
    {
        return a[i][j];
    }

    void initIden()
    {
        for ( int i = 0; i < N; ++i )
                a[i][i] = 1;
    }

    inline Matrix operator * ( const Matrix &B ) const
    {
        Matrix C( N );

        for ( int i = 0; i < N; ++i )
                for ( int j = 0; j < N; ++j )
                        for ( int k = 0; k < N; ++k )
                                C.a[i][j] = ( C.a[i][j] + 1LL * a[i][k] * B.a[k][j] ) % mod;

        return C;
    }

    bool operator == ( const Matrix B )
    {
        for ( int i = 0; i < N; ++i )
                for ( int j = 0; j < N; ++j )
                        a[i][j] = B.a[i][j];

        return true;
    }

    inline Matrix power( const int P )
    {
        Matrix sol( N );
        Matrix A = *this;
        sol.initIden();

        for ( int i = 0; ( 1 << i ) <= P; ++i )
        {
            if ( P & ( 1 << i ) )
                    sol = sol * A;

            A = A * A;
        }

        return sol;
    }
};

int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");

    int P;
    f >> P;

    Matrix A( 3 );
    A.set( 0, 0, 0 );
    A.set( 0, 1, 1 );
    A.set( 1, 0, 1 );
    A.set( 1, 1, 1 );

    A = A.power( P - 1 );

    g << A.print( 1, 1 ) << "\n";

    return 0;
}