#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
void initializare(long long a[3][3],int ok){
    if(ok==0){

        a[1][1]=1;
        a[1][2]=0;
        a[2][1]=0;
        a[2][2]=1;
    }
    else{
        a[1][1]=1;
        a[1][2]=1;
        a[2][1]=1;
        a[2][2]=0;
    }
}
void inmultire(long long a[3][3], long long b[3][3], long long c[3][3]){
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            c[i][j]=0;
            for(int k=1;k<=2;k++){
                c[i][j]+=a[i][k]*b[k][j];
                c[i][j]%=666013;
            }
        }
    }


}
void copiere(long long a[3][3], long long b[3][3]){
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            a[i][j]=b[i][j];
        }
    }

}
long long a[3][3],p[3][3],aux[3][3],n;
int main(){
    fin>>n;
    if(n<=2){
        fout<<"1";
    }
    n--;
    n--;
    initializare(a,1);
    initializare(p,1);
    while(n!=0){
        if(n%2==1){
            inmultire(a,p,aux);
            copiere(p,aux);
        }
        inmultire(a,a,aux);
        copiere(a,aux);
        n=n/2;
    }
    fout<<p[1][1];




}