#include<stdio.h>

int L=666013;
long long pr[2][2];

void prod(long long a[2][2], long long b[2][2]){
    int i,j;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            pr[i][j]=(a[i][0]*b[0][j]+a[i][1]*b[1][j])%L;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            a[i][j]=pr[i][j];
}

int main(){
    int n,rasp,i;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    long long a[2][2] = {{1,0},{0,1}};
    long long b[2][2] = {{0,1},{1,1}};
    for (i=0;i<30;++i) {
        if (1<<i&n)
            prod(a,b);
        prod(b,b);
    }
    printf("%d",a[0][1]);
    return 0;
}