#include <iostream>
#include <fstream>
#define m  666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
void main()
{
	int n=0;
	fin >> n;
	if (n == 0)
	{
		fout << 0;
		return;
	}
	if (n == 1 || n==2)
	{
		fout << 1;
		return;
	}
	struct matr{ int a,b,c; }x,t;
	x.a = 1, x.b = 0, x.c = 1;
	t.a = 0, t.b = 1, t.c = 1;
	int aux;
	for (n--; n; n >>= 1)
	{
		if (n & 1)
		{
			x.a = (x.a*t.a + x.b*t.b)%m;
			aux = x.b;
			x.b = (x.b*t.a + x.c*t.b)%m;
			x.c = (aux*t.b + x.c*t.c)%m;
		}
		aux=t.a;
		t.a = (t.b*t.b+t.a*t.a)%m;
		t.b = (aux*t.b + t.b*t.c)%m;
		t.c =( t.c*t.c + t.a-aux*aux)%m;
	}
	fout << x.c;
}