#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PRIM    666013

void eql(uint64_t dst[2][2],uint64_t src[2][2]){
    memcpy(dst,src,4 * sizeof(uint64_t));
}

uint64_t fibo(int x){
    uint64_t A[2][2],B[2][2],C[2][2];
    A[0][0] = 0, A[0][1] = A[1][0] = A[1][1] = 1;
    B[0][0] = B[1][1] = 1, B[0][1] = B[1][0] = 0;

    while(x){
        if(x & 1){
            C[0][0] = (B[0][0] * A[0][0] + B[0][1] * A[1][0]) % PRIM,
            C[0][1] = (B[0][0] * A[0][1] + B[0][1] * A[1][1]) % PRIM,
            C[1][0] = (B[1][0] * A[0][0] + B[1][1] * A[1][0]) % PRIM,
            C[1][1] = (B[1][0] * A[0][1] + B[1][1] * A[1][1]) % PRIM;
            eql(B,C);
        }
        C[0][0] = (A[0][0] * A[0][0] + A[0][1] * A[1][0]) % PRIM,
        C[0][1] = (A[0][0] * A[0][1] + A[0][1] * A[1][1]) % PRIM,
        C[1][0] = (A[1][0] * A[0][0] + A[1][1] * A[1][0]) % PRIM,
        C[1][1] = (A[1][0] * A[0][1] + A[1][1] * A[1][1]) % PRIM;
        eql(A,C);

        x >>= 1;
    }
    return B[1][0];
}

int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int n;
    scanf("%d",&n);
    printf("%llu\n",fibo(n));
    return 0;
}