#include<stdio.h>
#define MOD 666013
FILE *in,*out;
int N,z[3][3],sol[3][3],aux[3][3],q,j,i;
int main()
{
    in=fopen("kfib.in","rt");
    out=fopen("kfib.out","wt");
    fscanf(in,"%d",&N);
    N--;
    sol[0][0]=sol[1][1]=z[0][1]=z[1][0]=z[1][1]=1;
    for(i=0;(1LL<<i)<=N;i++)
    {
        if( ((1LL<<i) & N) )
        {
            for(q=0;q<=1;q++)
					for(j=0;j<=1;j++)
						aux[q][j]=(1LL*z[q][0]*sol[0][j] + 1LL*z[q][1]*sol[1][j])%MOD;
            for(q=0;q<=1;q++)
					for(j=0;j<=1;j++)
                        sol[q][j]=aux[q][j];
        }

        for(q=0;q<=1;q++)
            for(j=0;j<=1;j++)
                aux[q][j]=(1LL*z[q][0]*z[0][j] + 1LL*z[q][1]*z[1][j])%MOD;
        for(q=0;q<=1;q++)
            for(j=0;j<=1;j++)
                z[q][j]=aux[q][j];
    }
    fprintf(out,"%d",sol[1][1]);

    return 0;
}