#include <iostream>
#include <fstream>

using namespace std;

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

int k;
long long lem_atrice[1][2] =
{
	{1, 0}
};

long long da_matricea_ma[2][2] =
{
	{1, 1},
	{1, 0}
};

long long matrice_ajutat[2][2] =
{
	{1, 1},
	{1, 0}
};

long long da_matricea_la_sfarsit[2][2] =
{
	{1, 0},
	{0, 1}
};

void matrix_mul(long long matrix_a[][2], long long matrix_b[][2], long long len_l, long long len_c)
{
	long long matrix_c[2][2];
	for (int i = 0; i < len_l; ++i)
		for (int j = 0; j < len_c; ++j)
			matrix_c[i][j] = 0;

	for (int i = 0; i < len_l; ++i)
		for (int j = 0; j < len_c; ++j)
			for (int q = 0; q < len_c; ++q){
				matrix_c[i][j] += matrix_a[i][q]*matrix_b[q][j];
				matrix_c[i][j] %= 666013;
			}

	for (int i = 0; i < len_l; ++i)
		for (int j = 0; j < len_c; ++j)
			matrix_a[i][j] = matrix_c[i][j];
}

void Solve()
{
	for (int i = k-1; i > 0; i >>= 1){
		if (i%2 == 1)
			matrix_mul(da_matricea_la_sfarsit, matrice_ajutat, 2, 2);
		matrix_mul(matrice_ajutat, da_matricea_ma, 2, 2);
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j)
				da_matricea_ma[i][j] = matrice_ajutat[i][j];

	}
	matrix_mul(lem_atrice, da_matricea_la_sfarsit, 1, 2);
}

void Read()
{
	fin >> k;
}

void Write()
{
	fout << da_matricea_la_sfarsit[0][0];
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}