#include<stdio.h>

#define prime 666013
class mat22{
public:
	int matrix[2][2];
	
	mat22() { matrix[0][0] = matrix[0][1] = matrix[1][0] = matrix[1][1] = 0;};
	mat22(int val) {
		
		matrix[0][0] = matrix[1][1] = 1;
		matrix[0][1] = matrix[1][0] = 0;
		
		if( val == 1) 
			return ;
		matrix[1][0] = matrix[0][1] = 1;
		matrix[0][0] = 0;
		
		return;
		
	}
	mat22 operator*(const mat22&) const;
	mat22(const mat22 &source)
    {
		for(int i = 0; i < 2; ++i)
			for( int j = 0; j < 2; ++j)
				matrix[i][j] = source.matrix[i][j];
        
    }
  
};

mat22 mat22::operator* ( const mat22& a) const {
	mat22 b;
	for( int i = 0; i < 2; i++)
		for( int j = 0; j < 2; ++j)
			for( int l = 0; l < 2; ++l)
				b.matrix[i][j] = (b.matrix[i][j] + (long long) matrix[i][l] * a.matrix[l][j])% prime;
	return b;
}

int main() {
	
	int N;
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	scanf("%d", &N);
	if( N <= 2) {
		printf("%d\n", 1);
		return 0;
	}
	mat22 rez(1);
	mat22 val(0);
	
	int put = 1;
	while(N) {
		if( N & put) {
			N ^= put;
			rez = rez * val;
		}
		put <<= 1;
		val = val * val;
	}
	printf("%d\n", rez.matrix[1][0]);
	
	return 0;
}