#include<fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int k;
long long a[3][3],b[3][3],c[3][3];
void inmultire(long long d[3][3],long long f[3][3],long long g[3][3]){
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            g[i][j]=0;
            for (int q=0;q<=1;q++){
                g[i][j]+=d[i][q]*f[q][j];
                g[i][j]%=666013;
            }
        }
    }
}

void copiere(long long d[3][3],long long g[3][3]){
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            d[i][j]=g[i][j];
        }
    }
}

int main(){
    fin>>k;
    if(k==0){
        fout<<"0";
        return 0;
    }
    if(k==1){
        fout<<"1";
        return 0;
    }
    k--;
    a[0][0]=1;
    a[0][1]=1;
    a[1][0]=1;
    b[0][0]=1;
    b[1][1]=1;
    while(k>=1){
        if(k%2==1){
            inmultire(a,b,c);
            copiere(b,c);
        }
        inmultire(a,a,c);
        copiere(a,c);
        k/=2;
    }
    fout<<b[0][0];
    return 0;
}