#include<fstream>
#define mod 666013


using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");
long long r[3][3],I[3][3],R[3][3];
long long  n;
void copy  (long long C[3][3]){
   int i,j;
    for(i=1;i<=2;++i){
        for(j=1;j<=2;++j){

            C[i][j]=r[i][j];
        }
    }
}
void mult (long long  C[3][3],long long  B[3][3]) {
int i,j,k;
    for(i=1;i<=2;++i){

        for(k=1;k<=2;++k) {
            r[i][k]=0;

            for(j=1;j<=2;++j){

                    r[i][k]=r[i][k]+(C[i][j]*B[j][k])%mod ;

            }
             r[i][k]%=mod;
        }
    }
    copy(C);
}
void lg(long long  P[3][3],long long  A[3][3],int put){


    while( put ) {

        if(put%2==1){
            mult(P,A);
        }
        mult(A,A);
        put>>=1;
    }
}
int main () {

    f>>n;

    I[1][1]=I[2][2]=1;
    R[2][1]=R[1][2]=R[2][2]=1;
    lg(I,R,n-1);
    g<<(I[2][2])%mod;
    return 0;
}