#include <cstdio>
#include <cstdlib>
#include <string>

#define MODNR 666013

typedef int matrix[2][2];

FILE *fin=fopen("kfib.in","r");
FILE *fout=fopen("kfib.out","w");

inline void setidentity(matrix & m)
{
	m[0][0]=1; m[0][1]=0;
	m[1][0]=0; m[1][1]=1;
}

inline void setfactor(matrix & m)
{
	m[0][0]=0; m[0][1]=1;
	m[1][0]=1; m[1][1]=1;
}

inline void matrixmult(matrix & res, matrix & a, matrix &b)
{
	res[0][0]=((long long)a[0][0]*b[0][0]+(long long)a[0][1]*b[1][0])%MODNR;
	res[0][1]=((long long)a[0][0]*b[0][1]+(long long)a[0][1]*b[1][1])%MODNR;
	res[1][0]=((long long)a[1][0]*b[0][0]+(long long)a[1][1]*b[1][0])%MODNR;
	res[1][1]=((long long)a[1][0]*b[0][1]+(long long)a[1][1]*b[1][1])%MODNR;
}

void matrixput (matrix & m, int put)
{
	matrix ident;
	setidentity(m);
	setfactor(ident);
	for (int i=(sizeof(int)*8-2); i>=0; i--)
	{
		matrix tmp;
		memcpy(tmp,m,sizeof(matrix));
		matrixmult(m,tmp,tmp);
		if (put&(1<<i))
		{
			memcpy(tmp,m,sizeof(matrix));
			matrixmult(m,tmp,ident);
		}
	}
}

int main (int argc, char * const argv[]) {
	int n;
    fscanf(fin, "%d", &n);
	switch (n)
	{
		case 0:
			fprintf(fout, "0\n");
			break;
		case 1:
			fprintf(fout, "1\n");
			break;
		default:
			matrix m;
			matrixput(m,n-1);
			fprintf(fout, "%d\n", m[1][1]);
			break;
	}
	fclose(fin);
	fclose(fout);
    return 0;
}