#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 0
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
#endif // USE_STD_IO

const int MOD = 666013;
unordered_map<int, int> memo;
int k;

static inline int Fibo(int n) {
    if(1 >= n) return 1;
    if(memo.count(n)) return memo[n];
    int n2 = n / 2;
    if(1 == n % 2) {
        return memo[n] = (1LL * Fibo(n2 + 1) * Fibo(n2) + 1LL * Fibo(n2) * Fibo(n2 - 1)) % MOD;
    }
    else {
        return memo[n] = (1LL * Fibo(n2) * Fibo(n2) + 1LL * Fibo(n2 - 1) * Fibo(n2 - 1)) % MOD;
    }
}

int main() {
    if(USE_STD_IO) ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> k;
    fout << (0 == k ? 0 : Fibo(k - 1));

    return 0;
}