#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

int period[4 * MOD];
int sizePeriod;

int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    int K;
    in >> K;

    period[sizePeriod++] = 1;
    period[sizePeriod++] = 1;

    do
    {
        period[sizePeriod] = (period[sizePeriod - 1] + period[sizePeriod - 2]) % MOD;
        sizePeriod++;

    } while (period[sizePeriod - 1] != 1 || period[sizePeriod - 2] != 1);

    sizePeriod -= 2;

    out << period[(K - 1 + sizePeriod) % sizePeriod] << "\n";

    return 0;
}