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

ifstream f ("kfib.in");
ofstream g ("kfib.out");

const int MOD = 666013;
int k, P;
int *F;

void perioada() {
    int f0 = 0, f1 = 1, f2, per = 0;
    do {
        f2 = (f1+f0)%MOD;
        f0 = f1;
        f1 = f2;
        P ++;
    } while (f0 != 0 || f1 != 1);
}

void fibonacci() {
    F[0] = 0;
    F[1] = 1;
    for(int i=2; i<=P; i++)
        F[i] = (F[i-2] + F[i-1]) % MOD;
}

int main()
{
    f >> k;
    perioada();
    F = new int [P+1];
    fibonacci();
    g << F[k%P];
    f.close();
    g.close();
    return 0;
}