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

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

long long ans[ 3 ][ 3 ];
long long z[ 3 ][ 3 ];
long long a[ 3 ][ 3 ];
long long n;

void inm( long long sol[ 3 ][ 3 ], long long x[ 3 ][ 3 ] ) {
    for( int i = 1; i <= 2; i++ )
        for( int j = 1; j <= 2; j++ )
            for( int l = 1; l <= 2; l++ )
                z[ i ][ j ] += ( sol[ i ][ l ] * x[ l ][ j ] );

    for( int i = 1; i <= 2; i++ )
        for( int j = 1; j <= 2; j++ ) {
            sol[ i ][ j ] = z[ i ][ j ] % MOD;
            z[ i ][ j ] = 0;
        }
}

int main()
{
    cin >> n;
    a[ 1 ][ 1 ] = 0LL;
    a[ 1 ][ 2 ] = 1LL;
    a[ 2 ][ 1 ] = 1LL;
    a[ 2 ][ 2 ] = 1LL;

    ans[ 1 ][ 1 ] = 0LL;
    ans[ 1 ][ 1 ] = 1LL;

    long long p = n;
    long long put = 1;
    for( long long put = 1; p; put <<= 1LL ){
        if( p & put ) {
            inm( ans, a );
            p -= put;
        }
        inm( a, a );
    }

    cout << ans[ 1 ][ 2 ] << '\n';
    return 0;
}