#include <fstream>

using namespace std;

#define LL long long
#define mod 666013

struct Mat {
    LL a, b, d;
};

LL FastFibonacci(int x) {
    if (x <= 1)
        return x;

    Mat res = {1, 0, 1}, A = {0, 1, 1}, aux;
    for (int pow = x-1; pow != 0; pow >>= 1) {
        if ( pow & 1 ) {
            aux.a = (res.a * A.a + res.b * A.b) % mod;
            aux.b = (res.a * A.b + res.b * A.d) % mod;
            aux.d = (res.b * A.b + res.d * A.d) % mod;
            res = aux;
        }

        aux.a = (A.a * A.a + A.b * A.b) % mod;
        aux.b = (A.a * A.b + A.b * A.d) % mod;
        aux.d = (A.b * A.b + A.d * A.d) % mod;
        A = aux;
    }

    return res.d;
}

int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    int x;
    fin >> x;
    fout << FastFibonacci(x);
    return 0;
}