#include <fstream>

using namespace std;

class Vector
{
private:
	long long *vector;
	long long n;
public:
	Vector();
	Vector(long long n);
	Vector(Vector &V);

	long long &operator[] (long long i);
	long long Length();

	void init(long long n);
};

long long Vector::Length()
{
	return this->n;
}

Vector::Vector()
{
	init(1);
}

Vector::Vector(long long n)
{
	init(n);
}

Vector::Vector(Vector &V) : n(V.n)
{
	for (long long i = 0; i < n; i++)
		this[i] = V[i];
}

long long &Vector::operator[] (long long i)
{
	return vector[i];
}

void Vector::init(long long n)
{
	vector = new long long[n] {0};
	this->n = n;
}

class Matrix
{
private:
	Vector * matrix;
	long long n;
	void init(long long n);
public:
	Matrix(long long n);
	Matrix(Matrix &M);

	Matrix operator*(const Matrix &M);
	Matrix operator%(long long p);

	Matrix power(long long p, long long mod = 1);
	Vector & operator[](long long i);
};

void Matrix::init(long long n)
{
	matrix = new Vector[n];
	this -> n = n;
	for (long long i = 0; i < n; i++)
		matrix[i].init(n);
}

Matrix::Matrix(long long n)
{
	init(n);
}


Matrix::Matrix(Matrix &M)
{
	if (n != M.n)
		init(M.n);
	for (long long i = 0; i < n; i++)
		for (long long j = 0; j < n; j++)
			matrix[i][j] = M.matrix[i][j];
}

Matrix Matrix::operator*(const Matrix &M)
{
	Matrix R(n);
	for (long long i = 0; i < n; i++)
		for (long long j = 0; j < n; j++)
			for (long long k = 0; k < n; k++)
				R[i][j] += matrix[i][k] * M.matrix[k][j];
	return R;
}

Matrix Matrix::operator%(long long p)
{
	Matrix R(n);
	for (long long i = 0; i < n; i++)
		for (long long j = 0; j < n; j++)
			R[i][j] = matrix[i][j] % p;
	return R;
}

Matrix Matrix::power(long long p, long long mod)
{
	Matrix X = *this;
	while (!(p & 1))
	{
		X = X * X % mod;
		p /= 2;
	}
	Matrix R = X;
	p--;
	while (p)
	{
		if (p & 1)
		{
			R = R * X % mod;
			p--;
		}
		else
		{
			X = X * X % mod;
			p /= 2;
		}
	}
	return R;
}

Vector & Matrix::operator[](long long i)
{
	return matrix[i];
}

int main()
{
    long long p;
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f >> p;
	Matrix M(2);
	M[0][0] = 0;
	M[0][1] = M[1][0] = M[1][1] = 1;
	M = M.power(p, 666013);
	g << M[0][1];
    return 0;
}