#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

static inline pair <int, int> inmult( const pair<int, int>& a, const pair <int, int>& b ) {
    int x2 = (long long)a.first * b.first % MOD;
    return { ( (long long)a.first * b.second + (long long)a.second * b.first + x2 ) % MOD,
             ( (long long)a.second * b.second + x2 ) % MOD };
}
pair <int, int> lgput( pair <int, int> a, int b ) {
    pair <int, int> p = { 0, 1 };
    while ( b > 0 ) {
        if ( b % 2 == 1 ) {
            p = inmult( p, a );
        }
        a = inmult( a, a );
        b /= 2;
    }
    return p;
}
int main() {
    ifstream fin( "kfib.in" );
    ofstream fout( "kfib.out" );
    int k;
    fin >> k;
    fout << lgput( { 1, 0 }, k ).first;
    return 0;
}