#include <fstream>
#include <cstring>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int z[3][3],n,i,sol[3][3],mod=666013;

inline void inmult(int a[][3],int b[][3],int d[][3]) {
    int i,j,k;
    for (i=0;i<2;i++)
       for (j=0;j<2;j++)
          for (k=0;k<2;k++)
          d[i][j]=(d[i][j]+1LL*a[i][k]*b[k][j])%mod;
}
inline void logpow(int p, int s[][3]) {
    int c[3][3],aux[3][3],i;
    memcpy(c,z,sizeof(z));
    s[0][0]=s[1][1]=1;
    for (i=0;(1 << i) <=p;i++) {
        if(p & (1 << i) !=0) {
            memset(aux,0,sizeof(aux));
            inmult(s,c,aux);
            memcpy(s,aux,sizeof(aux));
        }
        memset(aux,0,sizeof(aux));
        inmult(c,c,aux);
        memcpy(c,aux,sizeof(c));
    }
}

int main () {
    f >> n;
    z[0][0]=0;z[0][1]=1; z[1][0]=1; z[1][1]=1;
    logpow(n-1,sol);
    g << sol[1][1] << '\n';
    f.close();g.close();
    return 0;
}