#include<stdio.h>
#define mod 666013
int mat[3][3],a[3][3];

void matmult (int a[3][3],int b[3][3])
{
	int c[3][3],i,j;
	
	for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
            c[i][j]=0 ;
		
	int k;	
	for (i=1;i<=2;++i)
			for (j=1;j<=2;++j)
				for(k=1;k<=2;++k)
					 c[i][j]=(c[i][j]+(a[i][k]*b[i][k])%mod)%mod;
    
	for (i=1;i<=2;i++)
        for (j=1;j<=2;j++)
            a[i][j]=c[i][j] ;
	}



int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	
	
	int n;
	scanf("%d",&n);
	a[1][2]=a[2][1]=a[2][2]=1;
	mat[1][1]=mat[2][2]=1;
	n--;
	
	while(n)
	{
			if (n&1)
	matmult(mat,a);
	matmult(a,a);
	n=n>>1;
	}
	
	printf("%d",mat[2][2]);
	}