#include <cstdio>

using namespace std;

const long long MOD = 666013;

struct Mat{
	long long mat[2][2];
};

Mat inmultire(Mat mat1, Mat mat2)
{
	Mat rez;
	rez.mat[0][0] = (mat1.mat[0][0] * mat2.mat[0][0] % MOD + mat1.mat[0][1] * mat2.mat[1][0] % MOD) % MOD;
	rez.mat[0][1] = (mat1.mat[0][0] * mat2.mat[0][1] % MOD + mat1.mat[0][1] * mat2.mat[1][1] % MOD) % MOD; 
	rez.mat[1][0] = (mat1.mat[1][0] * mat2.mat[0][0] % MOD + mat1.mat[1][1] * mat2.mat[1][0] % MOD) % MOD; 
	rez.mat[1][1] = (mat1.mat[1][0] * mat2.mat[0][1] % MOD + mat1.mat[1][1] * mat2.mat[1][1] % MOD) % MOD; 

	return rez;
}

long long n;

void citire()
{
	scanf("%lld", &n);
}

void afisare(Mat x)
{
	for(long long i = 0; i < 2; i++)
	{
		for(long long j = 0; j < 2; j++)
		{
			printf("%lld ", x.mat[i][j]);
		}		
		printf("\n");
	}			
	
	printf("\n");
}

Mat exponentiere(Mat mat, long long p)
{
	

	if(p == 1)
	{
		return mat;
	}

	if(p % 2 != 0)
	{
		return inmultire(mat, exponentiere(inmultire(mat, mat), p / 2));
	}
	else 
	{
		return exponentiere(inmultire(mat, mat), p / 2);
	}
}

void solve()
{
	Mat mat;	
	mat.mat[0][0] = 0;
	mat.mat[0][1] = 1;
	mat.mat[1][0] = 1;
	mat.mat[1][1] = 1;

	mat = exponentiere(mat, n - 1);

	printf("%lld", mat.mat[1][1]);
}

int main()
{
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	
	citire();
	solve();

	return 0;
}