#define mod 666013

#include<stdio.h>
#include<iostream>
#include<cstring>

long long mat[3][3];
void initmat()
{
	mat[1][1]=0;
	mat[1][2]=1;
	mat[2][1]=1;
	mat[2][2]=1;
}
void imultire_m(long long A[3][3], long long B[3][3], long long 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]=(C[i][j]+((long long)A[i][k]*B[j][k]))%mod;
}
void logpow(int power)
{
	long long aux[3][3],wow[3][3];
	memset(aux,0,sizeof(aux));
	aux[1][1]=aux[2][2]=1;
	memcpy(wow,aux,sizeof(aux));
	for(int i=0; (1<<i) <= power; i++)
	{
		if(power & (1<<i))
		{
			memset(wow,0,sizeof(wow));
			imultire_m(aux,mat,wow);
			memcpy(aux,wow,sizeof(wow));
		}
		memset(wow,0,sizeof(wow));
		imultire_m(mat,mat,wow);
		memcpy(mat,wow,sizeof(wow));
	}
	memcpy(mat,aux,sizeof(aux));
}

int main()
{
    int n,rez;
	FILE *f=fopen("kfib.in","r");
	FILE *g=fopen("kfib.out","w");
	fscanf(f,"%d",&n);
	if(n<=2)
		fprintf(g,"1");
	else
	{
			initmat();
	        logpow(n-2);
			rez=(((long long)mat[1][2]%mod)+((long long)mat[2][2]%mod))%mod;
	        fprintf(g,"%d",rez);
	}
}