#include<stdio.h>
#define MOD 666013

int a[][2]={{1,0},{0,1}};
int b[][2]={{1,1},{1,0}};

void multiply(int first[][2],int second[][2]){
    int i,j,k;
    int temp[2][2];
    for(i=0;i<2;i++){
        for(j=0;j<2;j++){
            temp[i][j]=0;
            for(k=0;k<2;k++){
                temp[i][j]=((((long long)first[i][k]*second[k][j])%MOD)+temp[i][j])%MOD;
            }
        }
    }
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            first[i][j]=temp[i][j];
}

int fib(long long K){
    if(K==0)
        return 1;
    else{
        fib(K/2);
        multiply(a,a);
        if(K&1)
            multiply(a,b);
    }
    return a[0][0];
}

int main(){
    long long K;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%lld",&K);
    printf("%d",K==0 ? 0 : fib(K-1));

    return 0;
}