#include<fstream>
#include<iostream>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");  
const int NMAX=2;

struct matrix{
    int mat[NMAX][NMAX];
    matrix(){
        mat[0][0]=0;
        mat[0][1]=0;
        mat[1][0]=0;
        mat[1][1]=0;
    };
};
matrix matriceIdentitate; 
matrix matriceBaza;
void precalc(){
    matriceIdentitate.mat[0][0]=1;
    matriceIdentitate.mat[1][1]=1;
    matriceIdentitate.mat[1][0]=0;
    matriceIdentitate.mat[0][1]=0;

    matriceBaza.mat[0][0]=0;
    matriceBaza.mat[1][1]=1;
    matriceBaza.mat[1][0]=1;
    matriceBaza.mat[0][1]=1;
}

matrix operator *(const matrix &a,const matrix &b){
    matrix rez;
    for(int i=0;i<NMAX;++i){
        for(int j=0;j<NMAX;++j){
            for(int k=0;k<NMAX;++k){
                rez.mat[i][j] = (rez.mat[i][j]+(1LL * a.mat[i][k] * b.mat[k][j])%MOD)%MOD; 
            }
        }
    }
    return rez;
}

matrix expRapida(matrix nr,int pow){
    if(pow==0){
        return matriceIdentitate;
    }
    if(pow % 2==1) {
        matrix rez=expRapida(nr, pow - 1);
        return nr * rez;
    }
    matrix p = expRapida(nr, pow / 2);
    return p * p;
}
int solve(){
    precalc();
    int n;
    fin>>n;
    matrix power=expRapida(matriceBaza,n-1);
    matrix init;
    init.mat[0][0]=0;
    init.mat[0][1]=1;
    init.mat[1][0]=0;
    init.mat[1][1]=0;
    matrix r=init*power;
    
    return (init* power).mat[0][1];
}
int main(){

    fout<<solve();
    return 0;
}