#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MOD 666013
using namespace std;

FILE*IN,*OUT;

int Pow;
typedef long long  Matrix[5][5];
Matrix Mat,Mult,aux;
void Multiply(Matrix &a,Matrix b,int X,int Y,int C)
{
	memset(aux,0,sizeof aux);
	for(int i=1;i<=X;i++)
		for(int j=1;j<=Y;j++)
			for(int k=1;k<=C;k++)
				aux[i][j]=(aux[i][j]+a[i][k]*b[k][j])%MOD;
	memcpy(a,aux,sizeof a);
}
void LogPow(Matrix &base,int exp)
{
	Matrix ans;
	memset(ans,0,sizeof ans);
	ans[1][1]=ans[2][2]=1;
	for(int i=0;i<32;i++)
	{
		if(exp&(1<<i))
			Multiply(ans,base,2,2,2);
		Multiply(base,base,2,2,2);
	}
	memcpy(base,ans,sizeof ans);
}
int main()
{
	IN=fopen("kfib.in","r");
	OUT=fopen("kfib.out","w");

	Mat[1][1]=0,Mat[1][2]=1;
	Mult[2][1]=Mult[1][2]=Mult[2][2]=1;
	fscanf(IN,"%d",&Pow);
	LogPow(Mult,Pow-1);
	Multiply(Mat,Mult,1,2,2);
	fprintf(OUT,"%d",Mat[1][2]);
	return 0;
}