#include <fstream>

using namespace std;

int a[3][3],m[3][3],n,k;

inline void inmultire(int a[3][3],int b[3][3])
{
    int i,j,k,c[3][3];c[0][0]=c[0][1]=c[1][0]=c[1][1]=0;
    for(i=0;i<2;++i) for(j=0;j<2;++j) for(k=0;k<2;++k) c[i][j]=(1LL*c[i][j]+1LL*a[i][k]*b[k][j])%666013;
    for(i=0;i<2;++i) for(j=0;j<2;++j) a[i][j]=c[i][j];
}
inline void pow(int a[3][3],int k,int m[3][3])
{
    if(!k) return;
    if(k&1)
    {
        --k;
        inmultire(m,a);
    }
    inmultire(a,a);
    pow(a,(k>>1),m);
}
int main()
{
    ifstream f("kfib.in");ofstream g("kfib.out");
    f>>k;
    if(k<2)
    {
       g<<k<<'\n';
       return 0;
    }
    k-=2;
    a[0][0]=0;a[0][1]=1;a[1][0]=1;a[1][1]=1;
    m[0][0]=0;m[0][1]=1;m[1][0]=1;m[1][1]=1;

    pow(a,k,m);
    g<<m[1][1]<<'\n';

    return 0;
}