#include <iostream>
#include <fstream>

#define MATRIX_SIZE 5
#define MODULO 666013
#define input "kfib.in"
#define output "kfib.out"

using namespace std;

ifstream in(input);
ofstream out(output);

class matrix
{
	public:
		int table[MATRIX_SIZE][MATRIX_SIZE], N, M;
};

matrix operator*(matrix a, matrix b)
{
	matrix c;
	for (int i = 1; i <= a.N; i++)
	for (int j = 1; j <= b.M; j++)
	{
		c.table[i][j] = 0;
		for (int k = 1; k <= a.M; k++)
			c.table[i][j] = (c.table[i][j] + a.table[i][k] * b.table[k][j]) % MODULO;
	}
	c.N = a.N, c.M = b.M;
	return c;
}

matrix logarithm_power(matrix base, int power)
{
	if (power == 1) return base;
	if (power % 2) return base * logarithm_power(base, power - 1);
	return logarithm_power(base * base, power / 2);
}

void Solve_Problem()
{
	int matrix_power;
	in >> matrix_power;
	matrix FIBO, Z;
	FIBO.N = 1, FIBO.M = 2, FIBO.table[1][1] = 0, FIBO.table[1][2] = 1;
	Z.N = 2, Z.M = 2, Z.table[1][1] = 0, Z.table[1][2] = 1, Z.table[2][1] = 1, Z.table[2][2] = 1;
	Z = logarithm_power(Z, matrix_power - 1);
	FIBO = FIBO * Z;
	out << FIBO.table[1][2] << "\n";
}


int main()
{
	Solve_Problem();
	return 0;
}