#include<fstream>

using namespace std;

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

const int mod = 666013;
const int nmax = 2;

class Matrice{
    public:
        long long a[ 2 ][ 2 ];

        Matrice operator * ( const Matrice &x ) const {
            Matrice sol;
            for( int i = 0; i < 2; ++ i ) {
                for( int j = 0; j < 2; ++ j ) {
                    sol.a[ i ][ j ] = 0;
                    for( int k = 0; k < 2; ++ k ) {
                        sol.a[ i ][ j ] += a[ i ][ k ] * x.a[ k ][ j ];
                        sol.a[ i ][ j ] %= mod;
                    }
                }
            }
            return sol;
        }

        Matrice lgput( int n ) {
            Matrice aux = *this, sol = *this;
            -- n;
            while ( n > 0 ) {
                if ( n & 1 ) {
                    sol = sol * aux;
                }
                n >>= 1;
                aux = aux * aux;
            }
            return sol;
        }
} f, i;

int main() {
    i.a[ 0 ][ 0 ] = 0; i.a[ 0 ][ 1 ] = 1;
    i.a[ 1 ][ 0 ] = i.a[ 1 ][ 1 ] = 0;

    f.a[ 0 ][ 0 ] = 0;
    f.a[ 0 ][ 1 ] = f.a[ 1 ][ 1 ] = f.a[ 1 ][ 0 ] = 1;

    int n;
    fin >> n;
    f = i * f.lgput( n );
    fout << f.a[ 0 ][ 0 ] << "\n";

    fin.close();
    fout.close();
    return 0;
}