#include <stdio.h>

void putere (int v[2][2], int u[2][2]){
	int i, j, k, rez[2][2] = {0};
	for (i = 0 ; i < 2 ; ++i){
		for (j = 0 ; j < 2 ; ++j){
			for (k = 0 ; k < 2 ; ++k){
				rez[i][j] += (v[i][k] * u[k][j]) % 666013;
			}
			rez[i][j] %= 666013;
		}
	}
	for (i = 0 ; i < 2 ; ++i){
		for (j = 0 ; j < 2 ; ++j){
			v[i][j] = rez[i][j];
		}
	}
}

int fibo (int n){
	int v[2][2] = {0, 1, 1, 1}, rez[2][2] = {0, 1, 1, 1}, neutral[2][2] = {0, 1, 1, 1};
	int i, j, put = 1;
	while (n > 0){
		while (put * 2 <= n){
			putere (v, v);
			put *= 2;
		}
		n -= put;
		put = 1;
		putere (rez, v);
		for (i = 0 ; i < 2 ; ++i){
			for (j = 0 ; j < 2 ; ++j){
				v[i][j] = neutral [i][j];
			}
		}
	}
	return rez[0][0];
}

int main (){
	freopen ("kfib.in", "r", stdin);
	freopen ("kfib.out", "w", stdout);
	int n;
	scanf ("%d", &n);
	printf ("%d\n", fibo (n));
}