#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define MOD 666013
#define NMAX 3

using namespace std;

ifstream in ( "kfib.in" );
ofstream out ( "kfib.out" );

int Mk[NMAX][NMAX],Sol[NMAX][NMAX],Initial_Matrix[NMAX][NMAX];
int N;

void Multiply ( int A[][NMAX] , int B[][NMAX] , int C[][NMAX])
{
	int i , j , 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[k][j] ) % MOD;
	
}

int main ( void )
{
	int i , j ;
	 in >> N  ;
	 Initial_Matrix[1][1] = 0 ; Initial_Matrix[1][2] = Initial_Matrix[2][1] = Initial_Matrix[2][2] = 1 ; 
     --N;	
    Sol[1][1] = Sol[2][2] = 1 ; 	 
	 for ( ;  N > 0 ;  )
	  {
		  if( N % 2 )
		  {
			  memset( Mk , 0 , sizeof( Mk) );
			  Multiply ( Sol , Initial_Matrix , Mk );
			  memcpy( Sol , Mk , sizeof(Sol) );
		  }
		memset( Mk , 0 , sizeof(Mk) );
		Multiply(Initial_Matrix,Initial_Matrix  , Mk);
		memcpy( Initial_Matrix , Mk , sizeof(Initial_Matrix) );
		N /= 2;
	  }
	 out << Sol[2][2] << "\n";
	 in.close();
	 out.close();
	 return 0;
}