#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int modulo = 666013;

int N;
int Mat[2][2] = {{1,0},{0,1}};
int Fib[2][2] = {{0,1},{1,1}};

void mul(int A[2][2],int B[2][2]) // A = A*B
{
	int C[2][2];

	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
		{
			C[i][j] = 0;
			for(int k=0;k<2;++k)
				C[i][j] = (C[i][j] + ((long long)A[i][k]*B[k][j]) % modulo) % modulo;
		}
		
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			A[i][j] = C[i][j];
}

int solve(int N)
{
	int b = N;
	while (b)
	{
		if (b%2 == 1)
		{
			mul(Mat,Fib);
			//Mat = Mat * fib;
		}
		mul(Fib,Fib);
		b = b/2;
		// fib = fib*fib
	}

	return Mat[0][1];
	// Mat * [1;1]
}

int main()
{
	ifstream fin;
	fin.open("kfib.in");
	ofstream fout;
	fout.open("kfib.out");

	fin >> N;
	fout << solve(N) << endl;

	fout.close();
	fin.close();
	return 0;
}