#include <fstream>
#include <cstring>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const long long MOD = 666013;

struct matrix {
	long long val[3][3];
	
	matrix() {
		memset (val, 0, sizeof(val));
	}
	matrix (int a, int b, int c, int d) {
		memset (val, 0, sizeof(val));
		val[1][1] = a;
		val[1][2] = b;
		val[2][1] = c;
		val[2][2] = d;
	}
	
	void inmulteste (matrix B, matrix C) {
		val[1][1] = (B.val[1][1] * C.val[1][1] + B.val[1][2] * C.val[2][1]) % MOD;
		val[1][2] = (B.val[1][1] * C.val[1][2] + B.val[1][2] * C.val[2][2]) % MOD;
		val[2][1] = (B.val[2][1] * C.val[1][1] + B.val[2][2] * C.val[2][1]) % MOD;
		val[2][2] = (B.val[2][1] * C.val[1][2] + B.val[2][2] * C.val[2][2]) % MOD;
	}
};

int k, F[3];
matrix Z (1, 0, 0, 1), Z_pow (0, 1, 1, 1);

void lgpow (int P) {
	while (P) {
		if (P % 2 == 1)
			Z.inmulteste (Z, Z_pow);
		Z_pow.inmulteste (Z_pow, Z_pow);
		P /= 2;
	}
}

int main() {
	F[0] = 0;		F[1] = 1;
	
	f >> k;
	lgpow (k - 1);
	
	int rez = (F[0] * Z.val[1][2] + F[1] * Z.val[2][2]) % MOD;
	g << rez << '\n';
	
	return 0;
}