#include<fstream>

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

long long I[4][4],F[4][2],rez[4][4],Ifin[4][4];
int n;

void init(){
    I[1][1]=I[1][3]=I[2][1]=I[2][2]=I[3][1]=0;
    I[1][2]=I[2][3]=I[3][2]=I[3][3]=1;

    F[1][1]=0;
    F[2][1]=F[3][1]=1;

    Ifin[1][1]=Ifin[2][2]=Ifin[3][3]=1;
}
void reset(){
     for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            rez[i][j]=0;
}
void prod_Ifin_I(){
    reset();
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                rez[i][j]+=Ifin[i][k]*I[k][j];
    }
}
void prod_I_I(){
    reset();
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++)
                rez[i][j]+=I[i][k]*I[k][j];
    }
}
void prod_Ifin_F(){
    reset();
    for(int i=1;i<=3;i++){
        for(int j=1;j<=1;j++)
            for(int k=1;k<=3;k++)
                rez[i][j]+=Ifin[i][k]*F[k][j];
    }
}
void sch_Ifin(){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            Ifin[i][j]=rez[i][j]%666013;
}
void sch_I(){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            I[i][j]=rez[i][j]%666013;
}
void power(int b){
    while(b!=0){
        if(b%2==1){
            prod_Ifin_I();
            sch_Ifin();
            b--;
        }
        else{
            prod_I_I();
            sch_I();
            b=b/2;
        }
    }
}
int main(){
    cin>>n;
    init();
    power(n-2);
    prod_Ifin_F();
    cout<<rez[3][1]%666013;
    return 0;
}