#include<fstream>


using namespace std;

#define max_n 2
#define ll long long
#define mod 666013

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

long long A[max_n][max_n] , sol[max_n][max_n] , temp[max_n][max_n] ; 

int n;

void initializare(){
	
	A[0][1] = A[1][0] = A[1][1] = 1;
	
	sol[0][0] = sol[1][1] = 1;
	
}

void multiply( ll A[max_n][max_n] , ll B[max_n][max_n] , ll C[max_n][max_n] ){
	
	int i , j , k;
	
	for( i = 0 ; i <  max_n ; i++){
		
		for( j = 0 ; j < max_n ; j++){
			
			C[i][j] = 0;
			
			for( k = 0 ; k < max_n ; k++ ){
				
				C[i][j] += (A[i][k] * B[k][j])%mod;
				
				C[i][j] %= mod;
				
			}
			
		}
		
	}
	
}

void solve(){
	
	
	while(n){
		
		if( n%2 == 1 ){
			
			multiply(sol , A , temp);
			
			memcpy( sol , temp , sizeof(temp));
			
		}
		
		
		multiply( A , A , temp );
		
		memcpy( A , temp , sizeof(temp) );
		
		n /= 2;
		
	}
	
	
}

void print(){
	
	
	fout << (sol[1][0] + sol[1][1]) % mod;
}

int main(){
	
	fin>>n;
	
	if( n < 3 )
		fout << "1";
	
	else{
		
		n -= 2;
		
		initializare();
		
		solve();
		
	}
	
	print();
	
	return 0;
}