//#include <iostream>
#include <fstream>
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
const int MOD=666013;
int rez[3][3],aux[3][3];
void seteaza_matrice(){
    rez[0][1]=1;
    aux[1][0]=1;
    aux[1][1]=1;
    aux[0][1]=1;
}
void inmult(int a[3][3],int b[3][3]){
    int c[3][3];
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            c[i][j]=0;
        }
    }
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                c[i][j]+=1LL*a[i][k]*b[k][j]%MOD;
                c[i][j]%=MOD;
            }
        }
    }
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            a[i][j]=c[i][j];
        }
    }
}
void lgput(int rez[3][3],int k){
    while(k!=0){
        if(k%2==1)
            inmult(rez,aux);
        inmult(aux,aux);
        k/=2;
    }
}
int main()
{
    seteaza_matrice();
    int k;
    cin>>k;
    lgput(rez,k);
    cout<<rez[0][0];
    /*for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            cout<<rez[i][j]<<" ";
        }
        cout<<"\n";
    }
    */
    return 0;
}