#include <stdio.h>

using namespace std;

#define MAX_LIN_COL 2
#define MOD 666013

int ans[MAX_LIN_COL][MAX_LIN_COL], mat[MAX_LIN_COL][MAX_LIN_COL], mat2[MAX_LIN_COL][MAX_LIN_COL];

void exp(int n){
    int lin, col, nr, flag=0;
    while(n){
        if(n&1){
            if(flag==0){
                for(lin=0;lin<MAX_LIN_COL;lin++){
                    for(col=0;col<MAX_LIN_COL;col++){
                        ans[lin][col]=mat[lin][col];
                    }
                }
                flag=1;
            }
            else{
                for(lin=0;lin<MAX_LIN_COL;lin++){
                    for(col=0;col<MAX_LIN_COL;col++){
                        for(nr=0;nr<MAX_LIN_COL;nr++){
                            mat2[lin][col]+=(long long)ans[lin][nr]*mat[nr][col]%MOD;
                            mat2[lin][col]%=MOD;
                        }
                    }
                }
                for(lin=0;lin<MAX_LIN_COL;lin++){
                    for(col=0;col<MAX_LIN_COL;col++){
                        ans[lin][col]=mat2[lin][col];
                        mat2[lin][col]=0;
                    }
                }
            }
        }
        for(lin=0;lin<MAX_LIN_COL;lin++){
            for(col=0;col<MAX_LIN_COL;col++){
                for(nr=0;nr<MAX_LIN_COL;nr++){
                    mat2[lin][col]+=(long long)mat[lin][nr]*mat[nr][col]%MOD;
                    mat2[lin][col]%=MOD;
                }
            }
        }
        for(lin=0;lin<MAX_LIN_COL;lin++){
            for(col=0;col<MAX_LIN_COL;col++){
                mat[lin][col]=mat2[lin][col];
                mat2[lin][col]=0;
            }
        }
        n/=2;
    }
}

int main()
{
    FILE *fin, *fout;
    int n;
    fin=fopen("kfib.in", "r");
    fscanf(fin, "%d", &n);
    fclose(fin);
    fout=fopen("kfib.out", "w");
    if(n==0){
        fprintf(fout, "0");
    }
    else{
        mat[0][0]=0;
        mat[0][1]=mat[1][0]=mat[1][1]=1;
        exp(n);
        fprintf(fout, "%d", ans[1][0]);
    }
    fclose(fout);
    return 0;
}