// https://infoarena.ro/problema/kfib
// Sa se calculeze al K-lea termen al sirului modulo 666013.

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

using namespace std;

// Functie care inmulteste doua matrice 2x2 si returneaza rezultatul modulo 666013
vector<vector <uint64_t>> InmultireMatrice(vector<vector <uint64_t>>& A, vector<vector <uint64_t>>& B)
{
	vector<vector <uint64_t>> C(2, vector<uint64_t>(2));
	
	C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % 666013;
	C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % 666013;
	C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % 666013;
	C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % 666013;

	return C;
}

// Functie care calculeaza puterea unei matrice A la exponentul dat prin exponentiere rapida
vector<vector <uint64_t>> ExponentiereMatrice(vector<vector <uint64_t>>& A, uint64_t exponent)
{
	vector<vector <uint64_t>> ans = { {1, 0}, {0, 1} }; // Initializam cu matricea identitate 2x2
	while (exponent > 0)
	{
		if (exponent % 2 == 1)
		{
			ans = InmultireMatrice(ans, A);
		}
		A = InmultireMatrice(A, A);
		exponent /= 2;
	}

	return ans;
}

// Functie care calculeaza al K-lea termen al sirului lui Fibonacci folosind matricea de transformare si exponentierea rapida
uint64_t KthFibonacci(uint64_t K)
{
	// Cazurile de baza
	if (K == 0)
		return 0;
	if (K == 1 || K == 2)
		return 1;

	vector<vector <uint64_t>> Z = { {0, 1}, {1, 1} };	// Matricea de transformare pentru sirul lui Fibonacci
	Z = ExponentiereMatrice(Z, K - 1);

	vector<vector <uint64_t>> F = { {0, 1}, {0, 0} }; // Matricea cu prima linie continand f(0) si f(1) (termenii 0 si 1 ai sirului Fibonacci)
	
	vector<vector <uint64_t>> rezultat = InmultireMatrice(F, Z);

	return rezultat[0][1]; // Elementul de pe prima linie si a doua coloana contine al K-lea termen al sirului Fibonacci
}


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

	if (!fin.is_open())
	{
		cerr << "Eroare la deschiderea fisierului de intrare!" << endl;
		return 1;
	}
	if (!fout.is_open())
	{
		cerr << "Eroare la deschiderea fisierului de iesire!" << endl;
		return 1;
	}

	uint64_t K;
	fin >> K;

	if (K < 0 || K > 1000000000) {
		cerr << "K trebuie sa fie in intervalul [0, 1000000000]!" << endl;
		return 1;
	}

	fout << KthFibonacci(K) % 666013 << endl;

	fin.close();
	fout.close();

    return 0;
}