#include<cstdio>
using namespace std;

const int MOD=666013;

long long kfib(long long k){
    long long mat[2][2],aux[2][2],c[2][2];
    mat[0][0]=0;
    mat[0][1]=mat[1][1]=mat[1][0]=1;
    aux[0][1]=aux[1][0]=0;
    aux[0][0]=aux[1][1]=1;
    while(k){
        if(k%2){
            c[0][0]=(aux[0][0]*mat[0][0]+aux[0][1]*mat[1][0])%MOD;
            c[0][1]=(aux[0][0]*mat[0][1]+aux[0][1]*mat[1][1])%MOD;
            c[1][0]=(aux[1][0]*mat[0][0]+aux[1][1]*mat[1][0])%MOD;
            c[1][1]=(aux[1][0]*mat[0][1]+aux[1][1]*mat[1][1])%MOD;
            for(int i=0;i<2;i++)
                for(int j=0;j<2;j++)
                    aux[i][j]=c[i][j];
        }
        c[0][0]=(mat[0][0]*mat[0][0]+mat[0][1]*mat[1][0])%MOD;
        c[0][1]=(mat[0][0]*mat[0][1]+mat[0][1]*mat[1][1])%MOD;
        c[1][0]=(mat[1][0]*mat[0][0]+mat[1][1]*mat[1][0])%MOD;
        c[1][1]=(mat[1][0]*mat[0][1]+mat[1][1]*mat[1][1])%MOD;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                mat[i][j]=c[i][j];
        k/=2;
    }
    return aux[1][0];
}

int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    long long k;
    scanf("%lld", &k);
    printf("%lld", kfib(k));
    return 0;
}