#include <cstdio>
using namespace std;
int v[1400005];

int main()
{

    bool ok = 0;
    int n, k;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d", &k);
    n = 2;
    v[1] = v[2] = 1;
    while(ok == 0) {
        v[++n] = (v[n - 1] + v[n - 2]) % 666013;
        if(v[n] == 1 && v[n - 1] == 1) {
            ok = 1;
            n -= 2;
        }
    }
    printf("%d\n", v[k % n]);
    return 0;
}