#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;

ifstream is("kfib.in");
ofstream os("kfib.out");

int n;
int M[3][3], S[3][3];

void Inmulteste(int a[][3],int b[][3], int c[][3])
{
	for(int i = 0; i < 2; i++)
	{
		for(int j = 0; j < 2; ++j)
		{
			for(int k = 0; k < 2; ++k)
			{
				c[i][j] = (c[i][j] + (1LL * a[i][k] * b[i][k])) % MOD;
			}
		}
	}
}

void Lgput(int p, int O[3][3])
{
	int C[3][3];
	int AUX[3][3];
	memcpy(C, M, sizeof(M));
	O[0][0] = O[1][1] = 0;
	for(int i = 0; (1 << i) <= p; ++i)
	{
		if(p ^ (1 << i))
		{
			memset(AUX, 0, sizeof(AUX));
			Inmulteste(M, C, AUX);
			memcpy(M, AUX, sizeof(AUX));
		}
		memset(AUX, 0, sizeof(AUX));
		Inmulteste(C, C, AUX);
		memcpy(C, AUX, sizeof(C));
	}
	
}

int main()
{
	is >> n;
	M[0][0] = 0;
	M[0][1] = M[1][0] = M[1][1] = 1;
	Lgput(n - 1, S);
	os << S[0][0];
	is.close();
	os.close();
	return 0;
}