#include <iostream>
#include <fstream>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int k;

struct str{
    long long f0, f1, f2, f3;
};

str rec(int put)
{
    str rsp;
    if (put <= 1)
    {
        rsp.f0 = 0; rsp.f1 = 1; rsp.f2 = 1; rsp.f3 = 1;
        return rsp;
    }
    if (put % 2 == 0)
    {
        str act = rec(put / 2);
        rsp.f0 = ((act.f0 * act.f0) % MOD + (act.f1 * act.f2) % MOD) % MOD;
        rsp.f1 = ((act.f0 * act.f1) % MOD + (act.f1 * act.f3) % MOD) % MOD;
        rsp.f2 = ((act.f2 * act.f0) % MOD + (act.f3 * act.f2) % MOD) % MOD;
        rsp.f3 = ((act.f2 * act.f1) % MOD + (act.f3 * act.f3) % MOD) % MOD;
        return rsp;
    }
    str act = rec(put - 1);
    rsp.f0 = act.f1;
    rsp.f1 = (act.f0 + act.f1) % MOD;
    rsp.f2 = act.f3;
    rsp.f3 = (act.f2 + act.f3) % MOD;
    return rsp;
}

int main()
{
    fin >> k;
    fout << rec(k).f1;

    return 0;
}