#include <fstream>
#include <cstring>

using namespace std;

ifstream cin ("kfib.in");
ofstream cout ("kfib.out");

const int MOD = 666013;

int f [5][5], c [5][5];

void matrixMultiply (int a[5][5], int b[5][5], int c[5][5]) {
	int i, j, k;
	int ans [5][5];

	for (i = 0; i < 2; i++) {
		for (j = 0; j < 2; j++) {
			ans [i][j] = 0;
			for (k = 0; k < 2; k++)
				ans [i][j] = (ans [i][j] + (1ll * a [i][k] * b [k][j]) % MOD) % MOD;
		}
	}

	memcpy (c, ans, sizeof (ans));
}


int main(){
	int k, i;

	cin >> k;
	f [0][0] = 0;
	f [0][1] = f [1][0] = f [1][1] = 1;

	c [0][0] = c [1][1] = 1;
	c [0][1] = c [1][0] = 0;

	for (; k; k >>= 1) {
		if (k & 1)
			matrixMultiply(c, f, c);
		matrixMultiply (f, f, f);
	}

	cout << c [0][1] << "\n";
	return 0;
}