#include <iostream>
#include <fstream>
#include <iterator>
#include <cmath>
using namespace std;

ifstream f;
ofstream g;

long long v[2000000];

double* matrix_mul(double *matrix1,int matrix1_i, int matrix1_j, double* matrix2, int matrix2_i, int matrix2_j)
{
	if (matrix1_j != matrix2_i)
		return nullptr;

	double *result = (double*)malloc(matrix1_i* matrix2_j * sizeof(double));

	int final_index = -1;
	for (int i = 0; i < matrix1_i; i++)
	{
		for (int j = 0; j < matrix2_j; j++)
		{
			final_index++;
			double current_result = 0;
			for (int k = 0; k < matrix2_i; k++)
			{
				current_result += *(matrix1 + ((i)*matrix1_j + k)) * *(matrix2 + ((k)*matrix2_j + j));
			}
		*(result + final_index) = current_result;
		}
	}

	return result;
}



int main()
{
	f.open("kfib.in");
	g.open("kfib.out");
	long long n;
	f >> n;

	v[0] = 0;
	v[1] = 1;
	//cea mai mare secventa
	long long result = (1 / sqrt(5)) * (pow((1 + sqrt(5)) / 2, n) - pow((1 - sqrt(5)) / 2, n));

	for (int i = 2; i <= 1332029; i++)
		//v[i] = (1 / sqrt(5)) * (pow((1 + sqrt(5)) / 2, i) - pow((1 - sqrt(5)) / 2, i));
		v[i] = (v[i - 1] + v[i - 2]) % 666013;

		/*
	for (int i = 3; i <= 1999998; i++)
		if (v[i] == 0 && v[i + 1] == 1)
			cout << i;
		*/
	g << v[n % 1332028]; 
	f.close();
	g.close();
	return 0;
}