#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int rez[3][3], A[3][3], X[3][3], n;
void inmultire(int A[3][3], int B[3][3], int l1, int c1, int l2, int c2)
{
	int R[3][3];
	memset(R, 0, sizeof(R));
	for (int i = 1; i <= l1; i++)
		for(int j=1;j<=c2;j++)
			for (int k = 1; k <= l2; k++)
				R[i][j] = (R[i][j]+(1LL*A[i][k] * B[k][j])%666013) % 666013;
	memcpy(A, R,sizeof(R));
}
void putere(int n, int A[3][3], int p)
{
	rez[1][1] = rez[2][2] = 1;
	rez[1][2] = rez[2][1] = 0;
	while (p)
	{
		if (p % 2)
			inmultire(rez, A, n, n, n, n);
		p /= 2;
		inmultire(A, A, n, n, n, n);
	}
}
void initializare()
{
	A[1][1] = A[1][2] = A[2][1] = 1;
	X[1][1] = 1;
}
int main()
{
	fin >> n;
	initializare();
	putere(2,A,n-1);
	inmultire(rez, X, 2, 2, 2, 1);
	fout << rez[1][1];
	return 0;
}