#include <bits/stdc++.h>

using namespace std;

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

const int mod = 666013;

struct matrice {
    int a, b, c, d;

    matrice () {
        a = 1;
        b = 1;
        c = 1;
        d = 0;
    }

    matrice operator * (matrice F) {
        matrice rezultat;

        rezultat.a = (1ll * F.a * a + 1ll * b * F.c) % mod;
        rezultat.b = (1ll * a * F.b + 1ll * b * F.d) % mod;
        rezultat.c = (1ll * a * F.c + 1ll * c * F.d) % mod;
        rezultat.d = (1ll * b * F.c + 1ll * d * F.d) % mod;


        return rezultat;
    }
};

matrice power (int n) {
    matrice p, a;

    p.a = p.d = 1;
    p.b = p.c = 0;

    while(n) {
        if(n % 2 == 1)
            p = p * a;
        a = a * a;
        n /= 2;
    }
    return p;
}

int main() {

    int n; fin >> n;

    matrice a;
    a = power(n-1);

    fout << a.a;

    return 0;
}