# include <fstream>
# include <cstring>
using namespace std;
ifstream f ("kfib.in");
ofstream g ("kfib.out");
int k, a[3][3], b[3][3], m[3][3];
void prod (int a[][3], int b[][3], int c[][3]){
	int i, j, k;
	for (i = 1; i <= 2; ++i)
		for (j = 1; j <= 2; ++j){
			for (k = 1; k <= 2; ++k)
				c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % 666013;
		}
}
void power_up (int a[][3], int k){
	a[1][1] = a[2][2] = 1;
	for (; k > 0; k >>= 1){
		if (k & 1){
			memset (m, 0, sizeof (m));
			prod (a, b, m);//b = a * b;
			memcpy (a, m, sizeof (m));
		}
		memset (m, 0, sizeof (m));
	    prod (b, b, m);//a = a * a;
		memcpy (b, m, sizeof (m));
	}
}
int main (){
	f >> k;
	b[1][2] = 1; b[2][1] = 1; b[2][2] = 1;
	power_up (a, k - 1);
	g << a[2][2] << '\n';
	g.close ();
	return 0;
}