#include <bits/stdc++.h>

using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
const long long modu=666013;
int i,j,ii,i2;long long suma,sol[4][4];
void inmultire_matrici (long long a[4][4],long long b[4][4])
{
	for(i=1;i<=2;++i)
		for(j=1;j<=2;++j)
		{
			suma=0;
			for(i2=1;i2<=2;++i2)
				suma=(suma+(a[i][i2]*b[i2][j])%modu)%modu;
			sol[i][j]=suma;
		}
	for(i=1;i<=2;++i)
		for(j=1;j<=2;++j)
			a[i][j]=sol[i][j];
}
void build_matnull (long long a[4][4])
{
	for(i=1;i<=2;++i)
		for(j=1;j<=2;++j)
			if(i==j)
				a[i][j]=1;
			else
				a[i][j]=0;
}
void build_mat1 (long long a[4][4])
{
	a[1][1]=0;a[1][2]=1;a[2][1]=1;a[2][2]=1;
}
void exponentiere (long long a[4][4],long long b[4][4],long long p)
{
	for(ii=0;p>0;ii++)
	{
		if((p & (1<<ii))!=0)
			p-=(1<<ii),inmultire_matrici(b,a);
		inmultire_matrici(a,a);
	}
}
int main ()
{
	long long k,fibo[3],mat1[4][4],mat2[4][4],ans;
	fin>>k;
	fibo[0]=0;fibo[1]=1;
	build_matnull(mat1);build_mat1(mat2);
	exponentiere(mat2,mat1,k);
	ans=((fibo[0]*mat1[1][1])%modu+(fibo[1]*mat1[2][1])%modu)%modu;
	fout<<ans;
	return 0;
}