#include <fstream>
#include <iostream>
using namespace std;

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

const long long mod = 666013;

struct mat {
    long long a, b, c, d;
};

int k;

mat exp(mat a, int b) {
    mat res;
    if(!b)
        res = {1LL,0,0,1LL};
    else if(b%2) {
        mat c = exp(a, b-1);
        res = {((a.a*c.a)%mod+(a.b*c.c)%mod)%mod, ((a.a*c.b)%mod+(a.b*c.d)%mod)%mod, ((a.c*c.a)%mod+(a.d*c.c)%mod)%mod, ((a.c*c.b)%mod+(a.d*c.d)%mod)%mod};
    } else {
        mat c = exp(a, b/2);
        res = {((c.a*c.a)%mod+(c.b*c.c)%mod)%mod, ((c.a*c.b)%mod+(c.b*c.d)%mod)%mod, ((c.c*c.a)%mod+(c.d*c.c)%mod)%mod, ((c.c*c.b)%mod+(c.d*c.d)%mod)%mod};
    }

    return res;
}

int main() {
    fin >> k;

    mat a = {0,1LL,1LL,1LL};
    fout << exp(a, k-1).d;
}