#include <fstream>
using namespace std;
/*
( 0, 1 ) ^ n  == ( F(n - 1), F(n) )
( 1, 1 )      == ( F(n), F(n + 1) )
 
( 0, 1 ) ^ n - 1 == ( F(n - 2), F(n - 1) )
( 1, 1 )         == ( F(n - 1), F(n) )
 */
const int MOD = 666013;
ifstream fin ( "fibo.in" );
ofstream fout ( "fibo.out" );
struct matrix {
    int a[2][2];
    void operator = ( const matrix &b ) {
        for ( int i = 0; i < 2; i++ )
            for ( int j = 0; j < 2; j++ )
                a[i][j] = b.a[i][j];
    }
    void operator *= ( const matrix &b ) {
        matrix rez;
        for ( int i = 0; i < 2; i++ )
            for ( int j = 0; j < 2; j++ ) {
                rez.a[i][j] = 0;
                for ( int k = 0; k < 2; k++ )
                    rez.a[i][j] += ( long long ) a[i][k] * b.a[k][j] % MOD;
                if ( rez.a[i][j] >= MOD )
                    rez.a[i][j] -= MOD;
            }
        *this = rez;
    }
    void operator ^= ( int put ) {
        matrix a, p = *this;
        a.a[0][0] = a.a[1][1] = 1; a.a[0][1] = a.a[1][0] = 0;
        while ( put > 0 ) {
            if ( put & 1 )
                a *= p;
            p *= p;
            put /= 2;
        }
        *this = a;
    }
};

int main () {
    int n;
    matrix sol;
    fin >> n;
    sol.a[0][0] = 0; sol.a[0][1] = sol.a[1][0] = sol.a[1][1] = 1;
    sol ^= n - 1;
    fout << sol.a[1][1];
    
    return 0;
}