#include<fstream>
#include <cstring>
using namespace std;
#define mod 666013
int mat[2][2], sol[2][2];

void matrix(int a[][2], int b[][2], int c[][2])
{
	int i,j,k;
	for(i=0;i<2;++i)
		for(j=0;j<2;++j)
			for(k=0;k<2;++k)
				c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%mod;
}

void lg_power(int p)
{
	mat[0][1]=mat[1][0]=mat[1][1]=1;
	int c[2][2], aux[2][2];
	memcpy(c,mat,sizeof(mat));
	
	for(;p;p>>=1)
	{
		if(p&1)
		{
			memset(aux,0,sizeof(aux));
			matrix(mat,c,aux);
			memcpy(mat,aux,sizeof(aux));
		}
		memset(aux,0,sizeof(aux));
		matrix(c,c,aux);
		memcpy(c,aux,sizeof(c));
	}
}
	
int main()
{
	ifstream fin("kfib.in");
	ofstream fout("kfib.out");
	int k;
    fin>>k;
	lg_power(k-1);
	
	fout<<mat[1][0];
}