#include<stdio.h>

#define M 666013

int v[4] = { 0, 1, 1, 1 };

void power(int n) {
    if(n!=1) {
        if(n%2) {
            n--;
            power(n/2);
            own_multiply();
            multiply();
        } else {
            power(n/2);
            own_multiply();
        }
    }
}

void own_multiply() {
    int aux[4];
    int i;
    for(i=0; i<4; i++) {
        aux[i] = v[i] % M;
    }
    v[0] = aux[0]*aux[0] + aux[1]*aux[2];
    v[1] = aux[0]*aux[1] + aux[1]*aux[3];
    v[2] = aux[2]*aux[0] + aux[3]*aux[2];
    v[3] = aux[2]*aux[1] + aux[3]*aux[3];
}

void multiply() {
    int aux[4];
    int i;
    for(i=0; i<4; i++) {
        aux[i] = v[i] % M;
    }
    v[0] = aux[1];
    v[1] = aux[0] + aux[1];
    v[2] = aux[3];
    v[3] = aux[2] + aux[3];
}

int main(void) {
    FILE *f;
    f = fopen("kfib.in", "r");
    if(f == NULL) {
        return 1;
    }
    int n;
    fscanf(f, "%d", &n);
    power(n-1);
    fclose(f);
    f = fopen("kfib.out", "w");
    if(f == NULL) {
        return 1;
    }
    fprintf(f, "%d\n", v[3]%M);
    fclose(f);
    return 0;
}