#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int mod = 666013;
const int MAXN = 10;
int N;
int M[MAXN][MAXN], I[MAXN][MAXN], f[MAXN][MAXN];

void mul(int A[MAXN][MAXN], int B[MAXN][MAXN]) {
	int aux[5][5];
	
	memset(aux, 0, sizeof(aux));
	
	for(int i = 1; i <= 2; ++i)
		for(int j = 1; j <= 2; ++j) 
			for(int k = 1; k <= 2; ++k) {
				aux[i][j] += (1LL * A[i][k] * B[k][j]) % mod;
				aux[i][j] %= mod;
			}
	
	for(int i = 1; i <= 2; ++i)
		for(int j = 1; j <= 2; ++j)
			A[i][j] = aux[i][j];
}
void debug(int A[MAXN][MAXN]) {
	
	for(int i = 1; i <= 2; ++i) {
		for(int j = 1; j <= 2; ++j)
			printf("%d ", A[i][j]);
		printf("\n");
	}
	
	printf("\n");
}
int main() {
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	
	scanf("%d\n", &N); --N;
	
	M[2][1] = M[1][2] = M[2][2] = 1;
	
	f[1][1] = 0;
	f[1][2] = 1;
	
	I[1][1] = I[2][2] = 1;
	
	for(int bit = 0; (1 << bit) <= N; ++bit) {
		if(N & (1 << bit))
			mul(I, M);
		mul(M, M);
		
	//	debug(I);
	}
	mul(f, I);
	
	printf("%d\n", f[1][2]);
	return 0;
}