#include<cstdio>
#define ll long long
#define M 666013

using namespace std;
class matrice {
	public: ll a, b, c, d;
	
	matrice() { a = b = c = d = 0; }	
 	matrice(ll a, ll b, ll c, ll d) {
		this->a = a;
		this->b = b;
		this->c = c;
		this->d = d;
	}
	
	matrice operator * (matrice B) {
		matrice m;
		
		m.a = (this->a * B.a + this->b * B.c) % M;
		m.b = (this->a * B.b + this->b * B.d) % M;
		m.c = (this->c * B.a + this->d * B.c) % M;
		m.d = (this->c * B.b + this->d * B.d) % M;
		
		return m;
	}
};

matrice A = matrice(0, 1, 1, 1);

matrice pow(int n) {
	if(n == 1) return A;
	if(n % 2 == 1) return A * pow(n - 1);
	
	matrice B = pow(n / 2);
	return B * B;
}

int main() {
	int n;
	
	freopen("kfib.in", "r", stdin), freopen("kfib.out", "w", stdout);
	scanf("%d", &n);
	
	matrice B = pow(n - 1);
	printf("%lld\n", B.d);
	
	return 0;
}