#include<stdio.h>
#include<stdlib.h>

int main()
{
	FILE *fin,*fout;
	unsigned long long a[2][2],d[2][2]={0};
	unsigned long long e[2][2]={0};
	int nr=0;
	int i,j,k;
	long x;
	unsigned long long c[2][2]={0};
	a[0][0]=0;
	a[0][1]=1;
	a[1][0]=1;
	a[1][1]=1;
	
	fin=fopen("kfib.in","r");
	fscanf(fin,"%ld",&x);
	while(x>0)
	{
		if(x & 1)
		{
			nr++;
			if(nr==1){
				e[0][0]=1;
				e[0][1]=0;
				e[1][0]=0;
				e[1][1]=1;
			}
			for(i=0;i<2;i++)
				for(j=0;j<2;j++)
				{	
					for(k=0;k<2;k++)
						d[i][j]+=(e[i][k]*a[k][j]%666013);
					d[i][j]=d[i][j]%666013;	
				}
			x--;
			
			for(i=0;i<2;i++)
				for(j=0;j<2;j++)
					e[i][j]=d[i][j];
	
			for(i=0;i<2;i++)
				for(j=0;j<2;j++)
					d[i][j]=0;
		
		}
		
			for(i=0;i<2;i++)
				for(j=0;j<2;j++)
					for(k=0;k<2;k++)
					{
						c[i][j]+=(a[i][k]*a[k][j]%666013);
						c[i][j]=c[i][j]%666013;
						
					}
			x=x>>1;
		
			for(i=0;i<2;i++)
				for(j=0;j<2;j++)
					a[i][j]=c[i][j];
			 for(i=0;i<2;i++)
					for(j=0;j<2;j++)
						c[i][j]=0;
		
	}
	
	fout=fopen("kfib.out","w");
	fprintf(fout,"%ld",e[0][1]);
	fclose(fin);
	fclose(fout);

}