#include <bits/stdc++.h>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int v[1500005];
int main()
{
    int n = 2, k, ok = 0;
    in >> k;
    v[1] = 1, v[2] = 1;
    while(ok == 0)
    {
        n ++;
        v[n] = (v[n - 1] + v[n - 2]) % 666013;
        if(v[n] == 1 && v[n - 1] == 1)
            ok = 1, n -= 2;
    }
    out << v[k % n];
    return 0;
}