#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#define MOD 666013

using namespace std;
using ll = long long;
template<typename T, size_t M, size_t N>
using matrix = array<array<T,M>,N>;

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

matrix<ll,2,2> rec = {1,1,1,0};
void multiplyMatrix (matrix<ll,2,2>& c, const matrix<ll,2,2> a, const matrix<ll,2,2> b) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                c[i][j] += (1ll * a[i][k] * b[k][j]) % MOD;
            }
        }
    }
}
void lgPut (matrix<ll,2,2>& c, int pw) {
    while (pw) {
        if (pw&1) {
            multiplyMatrix(c,rec,c);
        }
        multiplyMatrix(rec,rec,rec);
        pw >>= 1;
    }
}

int main() {
    int n;
    fin >> n;
    if (n == 0) {
        fout << 0;
        return 0;
    } else if (n == 1) {
        fout << 1;
        return 0;
    }
    matrix<ll,2,2> ans = {1,1,0,0};
    lgPut(ans,n-1);
    fout << ans[0][0];
    return 0;
}