#include<fstream>
#include<iostream>
#include<fstream>
using namespace std;
#define M 666013


void multiply(int a[2][2], int b[2][2])
{
	int mul[3][3];
	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			mul[i][j] = 0;
			for (int k = 0; k < 2; k++)
				mul[i][j] = (mul[i][j] + 1LL * a[i][k] * b[k][j]) % M;
		}
	}

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			a[i][j] = mul[i][j];
}

int power(int F[2][2], int n)
{
	int Mat[2][2] = { {0,1}, {1,1} };

	if (n == 1)
		return F[0][0] + F[0][1];

	power(F, n / 2);

	multiply(F, F);

	if (n % 2 != 0)
		multiply(F, Mat);

	return F[0][0] + F[0][1];
}

int findNthTerm(int n)
{
	int F[2][2] = { {0,1}, {1,1} };

	return power(F, n - 1);
}

int main()
{
	ifstream in;
	in.open("kfib.in");
	int n;
	in >> n;
	in.close();

	ofstream out;
	out.open("kfib.out");
	out << findNthTerm(n);
	out.close();
	return 0;

}