#include <fstream>
using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

#define mod 666013
#define Z 3

int n, sol[Z][Z], I[Z][Z] = {{0, 1, 0}, {1, 1, 0}, {0, 0, 0}};

inline void atrib (int a[][Z], int x) {
	for (int i = 0; i < Z; ++i)
		for (int j = 0; j < Z; ++j)
			a[i][j] = x;
}

inline void atrib(int a[][Z], int b[][Z]) {
	for (int i = 0; i < Z; ++i)
		for (int j = 0; j < Z; ++j)
			a[i][j] = b[i][j];
}

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

inline void pow(int p, int P[][Z]) {
	int c[Z][Z], aux[Z][Z];
	atrib(c, I);
	P[0][0] = P[1][1] = 1;
	for (int i = 1; i <= p; i <<= 1) {
		if (i & p) {
			atrib(aux, 0);
			multiply(P, c, aux);
			atrib(P, aux);
		}
		atrib(aux, 0);
		multiply(c, c, aux);
		atrib(c, aux);
	}
}
			
int main() {
	fin >> n;
	fin.close();
	pow(n - 1, sol);
	fout << sol[1][1];
	fout.close();
	return 0;
}