#include<stdio.h>
	#include<cstring>
	#define mod 666013
	FILE *f , *g ;
	long n , mat[3][3] , sol[3][3] , aux[3][3];
	
	void citire();
	void inmultire(long a[3][3] , long b[3][3] , long c[3][3]);
	void solve();
	void tipar();
	
	int main()
	{
		citire();
		solve();
		tipar();
		return 0;
	}
	
	void citire()
	{
		f=fopen("kfib.in"  , "r" ) ;
		fscanf(f , "%ld" , &n);
		fclose(f);
	}
	
	void solve()
	{
		mat[0][0] = 0 ; mat[0][1] = 1; mat[1][0] = 1 ; mat[1][1] = 1;
		sol[0][0] = sol[1][1] = 1;
		for ( int i = 0 ; (1<<i) <= n-1 ; ++i )
		{
			if((1 << i) & n-1)
			{
				memset(aux , 0 , sizeof(aux));
				inmultire(sol,mat,aux);
				memcpy(sol , aux , sizeof(aux));
			}
			memset(aux , 0 , sizeof(aux));
			inmultire(mat,mat,aux);
			memcpy(mat,aux,sizeof(aux));
		}
	}
	
	void inmultire( long a[3][3] , long b[3][3] , long c[3][3])
	{
		for ( int i = 0 ; i<= 1 ; ++i )
			for ( int j =  0 ; j <= 1 ; ++j )
				for ( int k = 0 ; k<= 1 ; ++k )
				  c[i][j] = (c[i][j] + a[i][k]*b[k][j])%mod;
	}
	
	void tipar()
	{
		g=fopen("kfib.out" , "w" );
		fprintf(g , "%ld" , sol[1][1] );
		fclose(g);
	}