#include <iostream>
#define MOD %666013

using namespace std;

int n;

class Matrix{
public:
	long long A[2][2];
	
	Matrix(){ }

	Matrix(long long a, long long b, long long c, long long d){
		A[0][0] = a; A[0][1] = b;
		A[1][0] = c; A[1][1] = d;
	}

	Matrix& operator=(const Matrix &m){
		A[0][0] = m.A[0][0];
		A[0][1] = m.A[0][1];
		A[1][0] = m.A[1][0];
		A[1][1] = m.A[1][1];
		return *this;
	}

	Matrix& operator*(const Matrix &m){
		long long B[2][2];
		B[0][0] = (A[0][0] * m.A[0][0])MOD + (A[0][1] * m.A[1][0])MOD;
		B[0][1] = (A[0][0] * m.A[0][1])MOD + (A[0][1] * m.A[1][1])MOD;
		B[1][0] = (A[1][0] * m.A[0][0])MOD + (A[1][1] * m.A[1][0])MOD;
		B[1][1] = (A[1][0] * m.A[0][1])MOD + (A[1][1] * m.A[1][1])MOD;
		A[0][0] = (B[0][0])MOD;
		A[0][1] = (B[0][1])MOD;
		A[1][0] = (B[1][0])MOD;
		A[1][1] = (B[1][1])MOD;
		return *this;
	}

	long long result(){
		return (A[0][1] + A[1][1]) MOD;
	}
};

Matrix A(0,1,1,1), I2(1,0,0,1);

Matrix power(int k){
	Matrix X;
	X = I2;
	if (k == 0) return X;
	while(k){
		if(k % 2 == 1){
			X = X * A;
		}
		A = A * A;
		k /= 2;
	}
	return X;
}

int main(){
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	int k;
	//cin >> k;
	scanf("%d", &k);

	if(k == 0) 
		printf("0");
	else
		if(k == 1){ 
			printf("1");
		}else{
			A = power(k-2);
			printf("%ld\n", A.result());
		}
	return 0;
}