#include <iostream>
#include <fstream>
#define M 666013

using namespace std;

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

class Matrix{
private:
	long long **matrix, size;
public:
	Matrix();
	Matrix(long long newSize);
	Matrix(long long newSize, long long **newMatrix);
	long long getSize();
    long long getElement(long long i, long long j);
	Matrix &operator=(const Matrix &newMatrix);
	Matrix operator+(const Matrix &matrixToAdd);
	Matrix operator-(const Matrix &matrixToSubtract);
	Matrix operator*(const Matrix &matrixToMultiply);
	Matrix operator^(long long power);
	friend istream &operator>> (istream &fin, Matrix &newMatrix);
	friend ostream &operator<< (ostream &fout, const Matrix &newMatrix);
};

Matrix::Matrix() {
	size = 0;
}

Matrix::Matrix(long long newSize) {
	size = newSize;
	matrix = new long long*[newSize+1];
	for (long long i=1; i<=newSize; i++)
    	matrix[i] = new long long[newSize+1];
}

Matrix::Matrix(long long newSize, long long **newMatrix) {
	size = newSize;
	matrix = new long long*[size+1];
	for (long long i=1; i<=size; i++)
    	matrix[i] = new long long[size+1];
	for (long long i=1; i<=size; i++)
    	for (long long j=1; j<=size; j++)
        	matrix[i][j] = newMatrix[i][j];
}

long long Matrix::getSize() {
	return size;
}

long long Matrix::getElement(long long i, long long j) {
    return matrix[i][j];
}

Matrix &Matrix::operator=(const Matrix &newMatrix) {
	if (size!=newMatrix.size)
	{
	    if (size)
        {
            for (long long i=1; i<=size; i++)
                delete [] matrix[i];
            delete [] matrix;
        }
    	size = newMatrix.size;
    	matrix = new long long*[size+1];
    	for (long long i=1; i<=size; i++)
        	matrix[i] = new long long[size+1];
	}
	for (long long i=1; i<=size; i++)
    	for (long long j=1; j<=size; j++)
        	matrix[i][j] = newMatrix.matrix[i][j];
	return *this;
}

Matrix Matrix::operator+(const Matrix &matrixToAdd) {
	Matrix sum(size);
	for (long long i=1; i<=size; i++)
    	for (long long j=1; j<=size; j++)
        	sum.matrix[i][j] = matrix[i][j] + matrixToAdd.matrix[i][j];
	return sum;
}

Matrix Matrix::operator-(const Matrix &matrixToSubtract) {
	Matrix diff(size);
	for (long long i=1; i<=size; i++)
    	for (long long j=1; j<=size; j++)
        	diff.matrix[i][j] = matrix[i][j] + matrixToSubtract.matrix[i][j];
	return diff;
}

Matrix Matrix::operator*(const Matrix &matrixToMultiply) {
    Matrix product(size);
    for (long long i=1; i<=size; i++)
        for (long long j=1; j<=size; j++)
        {
            product.matrix[i][j] = 0;
            for (long long k=1; k<=size; k++)
                product.matrix[i][j] = ((product.matrix[i][j]%M) + ((matrix[i][k]%M) * (matrixToMultiply.matrix[k][j]%M))%M)%M;
        }
    return product;
}

Matrix Matrix::operator^(long long power) {
    Matrix product, solution(2);
    product = *this;
    solution.matrix[1][1] = 1;
    solution.matrix[1][2] = 0;
    solution.matrix[2][1] = 0;
    solution.matrix[2][2] = 1;
    while (power)
    {
        if (power%2)
            solution = solution * product;
        product = product * product;
        power /= 2;
    }
    return solution;
}
/**
Matrix Matrix::operator^(long long power) {
    Matrix product;
    product = *this;
    for (long long i=1; i<power; i++)
        product = product * *this;
    return product;
}
*/
istream &operator>> (istream &fin, Matrix &newMatrix) {
	if (!newMatrix.size)
    	fin >> newMatrix.size;
	newMatrix.matrix = new long long*[newMatrix.size+1];
	for (long long i=1; i<=newMatrix.size; i++)
    	newMatrix.matrix[i] = new long long[newMatrix.size+1];
	for (long long i=1; i<=newMatrix.size; i++)
    	for (long long j=1; j<=newMatrix.size; j++)
        	fin >> newMatrix.matrix[i][j];
	return fin;
}

ostream &operator<< (ostream &fout, const Matrix &newMatrix) {
	fout << newMatrix.size << "\n";
	for (long long i=1; i<=newMatrix.size; i++)
    	for (long long j=1; j<=newMatrix.size; j++)
        	fout << newMatrix.matrix[i][j] << " \n"[j==newMatrix.size];
	return fout;
}

int main()
{
    long long number, **values;
    values = new long long*[3];
    values[1] = new long long[3];
    values[2] = new long long[3];
    values[1][1] = 0;
    values[1][2] = 1;
    values[2][1] = 1;
    values[2][2] = 1;
    Matrix solution(2, values);
    fin >> number;
    solution = solution ^ number;
    fout << solution.getElement(1, 2);
    return 0;
}