#include<cstdio>
#include<cstring>
using namespace std;
// 1LL - inseamna 1 definit pe long long, face conversia

#define mod 666013
int z[2][2] = { {0, 1}, {1, 1} };
int sol[2][2];

void mult(int a[][2], int b[][2], int c[][2]) {
	int i, j, k;
	for(i = 0; i < 2; ++i)
		for(j = 0; j < 2; ++j)
			for(k = 0; k < 2; ++k)
				c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
}

void putk(int p, int m[2][2]) {
	int ax[2][2], i;
	m[0][0] = m[1][1] = 1;
	for(i = 0; (1 << i) <= p; ++i) {
		if(p & (1 << i)) {
			memset(ax, 0, sizeof(ax));
			mult(m, z, ax);
			memcpy(m, ax, sizeof(ax));
		}
		memset(ax, 0, sizeof(ax));
		mult(z, z, ax);
		memcpy(z, ax, sizeof(z));
	}
}
	

int main() {
	int n;
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	scanf("%d", &n);
	putk(n - 1, sol);
	printf("%d", sol[1][1]);
	return 0;
}