// Al k-lea termen Fibonacci.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"
#include <cstdio> 
#include <cstring>

FILE *f=fopen("kfib.in", "r");
FILE *g=fopen("kfib.out", "w");


int k, p=666013;

int sol[3][3], mat[3][3]={{0, 0, 0},{0, 0, 1},{0, 1, 1}};


inline void inmultire(int a[3][3], int b[3][3], int c[3][3])
{
	for (int i=1; i<=2; ++i)
		for (int j=1; j<=2; ++j)
			for (int k=1; k<=2; ++k)
				c[i][j]+=(1LL*a[i][k]*b[k][j])%p;
}

void program()
{
	int act[3][3], aux[3][3];
	memcpy(act, mat, sizeof(mat));
	sol[1][1]=sol[2][2]=1;
	for (int i=0; (1<<i)<=k-1; ++i)
	{
		if ( (1<<i)&(k-1))
		{
			memset(aux, 0, sizeof(aux));
			inmultire(sol, act, aux);
			memcpy(sol, aux, sizeof(aux));			
		}
		memset(aux, 0, sizeof(aux));
		inmultire(act, act, aux);
		memcpy(act, aux, sizeof(aux));
	}
}





void read()
{
	fscanf(f, "%d", &k);
}


int main()
{
	read();
	program();
	fprintf(g, "%d", sol[2][2]%p);
	return 0;
}