#include <fstream>
#define mod 666013
using namespace std;

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

int k = 0;
long long sol[ 2 ][ 2 ] = { { 1, 0 }, { 0, 1 } },
c[ 2 ][ 2 ] = { { 0, 1 }, { 1, 1 } }, a[ 2 ][ 2 ] = { { 1, 1 }, { 0, 0 } };

void inmultire( long long a[ 2 ][ 2 ], long long b[ 2 ][ 2 ] )
{
    long long 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 ] = (c[ i ][ j ] + ( a[ i ][ k ] * b[ k ][ j ] % mod )) % mod;
        }
    for ( int i = 0; i < 2; ++ i )
        for ( int j = 0; j < 2; ++ j )
            a[ i ][ j ] = c[ i ][ j ];
}

void ridicare_la_putere( int n )
{
    while ( n )
    {
        if ( n % 2 == 1 )
        {
            n --;
            inmultire( sol, c );
        }
        else
        {
            n = (n / 2);
            inmultire( c, c );
        }
    }

    inmultire( a, sol );

    g << a[ 0 ][ 0 ];
}

int main()
{
    f >> k;

    ridicare_la_putere( k - 1 );
    return 0;
}