#include <cstdio>
#define MOD 666013
long long z[2][2]={{0,1},{1,1}},a[1][2]={0,1};
inline void inmult(long long a[][2],long long b[][2],int m,int n,int p)
{
    long long aux[m][p];
    for(int i=0;i<m;i++)
        for(int j=0;j<p;j++)
            aux[i][j]=0;
    for(int i=0;i<m;i++)
        for(int j=0;j<p;j++)
            for(int k=0;k<n;k++)
            {
                aux[i][j]+=(a[i][k]*b[k][j])%MOD;
                aux[i][j]%=MOD;
            }
    for(int i=0;i<m;i++)
        for(int j=0;j<p;j++)
            a[i][j]=aux[i][j];
}
inline void lgput(int n)
{
    while(n)
    {
        if(n&1)
            inmult(a,z,1,2,2);
        inmult(z,z,2,2,2);
        n>>=1;
    }
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("kfib.in","r");
    fout=fopen("kfib.out","w");
    int n;
    fscanf(fin,"%d",&n);
    if(n<2)
        fprintf(fout,"1");
    else
    {
        lgput(n-1);
        fprintf(fout,"%lld",a[0][1]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}