#include <fstream>
using namespace std;
ifstream in("kfib.in"); ofstream out("kfib.out");
#define NMAX 1400001

int v[NMAX];
int N;

int formare() {
    int i = 2;
    while(!(v[i] == 1 and v[i-1] == 0)) {
        i++;
        v[i] = (v[i-1] + v[i-2])%666013;
    }
    return i - 1;
}

int main(){

    in >> N;
    v[0] = 0;
    v[1] = v[2] = 1;

    int perioada = formare();
    out << v[N%perioada];

    return 0;
}