#include<cstdio>
#include<cstring>
using namespace std;
const int mod = 666013;
int k,e,sol[3][3],a[3][3],aux[3][3],i;
void mult(int c[3][3],int a[3][3],int b[3][3])
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%mod;
}
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&k); e=k-2;
	if(!k) {printf("0\n"); return 0;}
	sol[1][1]=sol[2][2]=1;
	a[1][2]=a[2][1]=a[2][2]=1;
	for(i=1;i<=e;i<<=1)
	{
	    if(i&e)
	    {
	        memset(aux,0,sizeof(aux));
	        mult(aux,sol,a);
	        memcpy(sol,aux,sizeof(aux));
	    }
	    memset(aux,0,sizeof(aux));
        mult(aux,a,a);
        memcpy(a,aux,sizeof(aux));
	}
	printf("%d\n",(sol[1][2]+sol[2][2])%mod);
	return 0;
}