#include <stdio.h>
#define mod 666013
using namespace std;
FILE *f=fopen("kfib.in","r"), *g=fopen("kfib.out","w");
void inmultire(long long int a[][2], long long int b[][2])
{
	long long int q,w,e,r;
	q=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%mod;
	r=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%mod;
	e=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%mod;
	w=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod;
	a[0][0]=q;
	a[0][1]=r;
	a[1][0]=e;
	a[1][1]=w;
}
int main()
{
	long long int j, i, a[2][2], b[2][2], p;
	fscanf(f,"%lld",&p);
	if(p==1||p==2)
		b[1][1]=1;
	else
		if(p==3)
			b[1][1]=2;
		else
			{
				for(i=0;i<=1;i++)
					for(j=0;j<=1;j++)
					{
						b[i][j]=1;
						a[i][j]=1;
					}
				a[0][0]=b[0][0]=0;
				p-=2;
				for(i=0;(1<<i)<=p;i++)
				{
					if((1<<i)&p)
						inmultire(b, a);
					inmultire(a, a);
				}
			}
	fprintf(g, "%lld", b[1][1]);
	return 0;
}