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

using namespace std;

const int MOD = 666013;

class Matrix {
	vector< vector<int> > mContent;

public:
	int NrLines, NrColumns;

	Matrix(int n, int m) : NrLines(n), NrColumns(m) {
		mContent.resize(NrLines);

		for (int line = 0; line < NrLines; ++line)
			mContent[line].resize(NrColumns);
	}

	int& ElementAt(int x, int y) {
		return mContent[x][y];
	}

	static Matrix GetUnitMatrix(int n) {
		Matrix unitMatrix(n, n);

		for (int i = 0; i < n; ++i)
			unitMatrix.ElementAt(i, i) = 1;

		return unitMatrix;
	}

	friend Matrix operator* (Matrix& first, Matrix& second) {
		Matrix result(first.NrLines, second.NrColumns);

		for (int i = 0; i < first.NrLines; ++i) {
			for (int j = 0; j < second.NrColumns; ++j) {
				result.ElementAt(i, j) = 0;
				for (int k = 0; k < first.NrColumns; ++k) {
					result.ElementAt(i, j) = (result.ElementAt(i, j) + first.ElementAt(i, k) * 1LL * second.ElementAt(k, j)) % MOD;
				}
			}
		}

		return result;
	}

	friend Matrix operator^ (Matrix& matrix, int power) {
		Matrix result = GetUnitMatrix(matrix.NrLines);

		while (power > 0) {
			if (power & 1) {
				result = result * matrix;
			}

			matrix = matrix * matrix;
			power >>= 1;
		}

		return result;
	}
};

int main() {
    ios::sync_with_stdio(false);

    ifstream cin("kfib.in");
    ofstream cout("kfib.out");

    int n;
    cin >> n;

    Matrix mat(2, 2);
    mat.ElementAt(0, 0) = 0;
    mat.ElementAt(0, 1) = 1;
    mat.ElementAt(1, 0) = 1;
    mat.ElementAt(1, 1) = 1;

    Matrix f(1, 2);
    f.ElementAt(0, 0) = 0;
    f.ElementAt(0, 1) = 1;

	mat = mat ^ n;

    cout << (f * mat).ElementAt(0, 0);
	//cout.flush();

    return 0;
}