#include<cstdio>
#include<string>
#define mod 666013
using namespace std;

void citeste();
void powlog();
//void prod(int[][],int[][],int[][]);
//void afiseaza();

int n;
int r;

int f[100];




void citeste()
{
	freopen("kfib.in","r",stdin);
	
	scanf("%d",&n);
	
	fclose(stdin);
}


void prod(int a[3][3], int b[3][3])
{
	int c[3][3];
	
	memset(c,0,sizeof(c));
	
	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] + a[i][k]*b[k][j] ) %mod;
	
	memcpy(a,c,sizeof(c));	
}


void powlog()
{
	n++;
	while(n)
	{
		f[0]++;
		if(n%2) f[f[0]]=1;
		n/=2;
	}	

	int x[3][3],d[3][3];
	
	memset(x,0,sizeof(x));
	memset(d,0,sizeof(d));

	x[1][2]=x[2][1]=x[2][2]=d[1][2]=d[2][1]=d[2][2]=1;
	
    for(int i=f[0];i>=1;i--)
	{
		if(i<f[0])prod(d,d);
		
		if(f[i] && i< f[0]) prod(d,x); 
	}	
    r=d[1][1];	
}


void afiseaza()
{
	freopen("kfib.out","w",stdout);
	
	printf("%d",r);
	
	fclose(stdout);
}

int main()
{
	citeste();
	powlog();
	afiseaza();
	
	return 0;
}