#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

struct mat {
    int a[2][2];

    mat() {
        a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0;
    }
    void diag( int x = 1 ) {
        a[0][0] = a[1][1] = x;
    }
};
mat operator * ( mat a, mat b ) {
    mat c;
    for ( int i = 0; i < 2; i ++ ) {
        for ( int j = 0; j < 2; j ++ ) {
            for ( int k = 0; k < 2; k ++ ) {
                c.a[i][j] = ( c.a[i][j] + (long long)a.a[i][k] * b.a[k][j] ) % MOD;
            }
        }
    }
    return c;
}
mat lgput( mat a, int b ) {
    mat c;
    c.diag();
    while ( b > 0 ) {
        if ( b % 2 ) {
            c = c * a;
        }
        a = a * a;
        b /= 2;
    }
    return c;
}
int main() {
    ifstream fin( "kfib.in" );
    ofstream fout( "kfib.out" );
    int n;
    fin >> n;
    mat a;
    a.a[0][1] = a.a[1][0] = a.a[1][1] = 1;

    a = lgput( a, n );
    fout << a.a[0][1] << '\n';
    return 0;
}