#include <fstream>
#include <cstring>

using namespace std;

#define MOD 666013

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

int N, A[3][3];

void inmult(int B[3][3], int A[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] + 1LL*A[i][k] * B[k][j]) % MOD;

	memcpy(B, C, sizeof C);

}

void pow(int A[3][3], int N)
{
	int B[3][3];
	B[1][1] = B[2][2] = 1;
	B[1][2] = B[2][1] = 0;

	for(; N; N >>= 1)
	{
		if(N & 1)
			inmult(B, A);

		inmult(A, A);
	}

	fout << B[2][1];
}

int main()
{
	fin >> N;

	A[1][1] = A[1][2] = A[2][1] = 1;
	pow(A, N);
}