#include <fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long a11,a12,a21,a22,b11,b12,b21,b22,p11,p12,p21,p22,k,m=666015;

void cit(),rez();

int main()
{
	cit();
	rez();
	return 0;
}

void cit()
{


	fin>>k;
}

void rez()
{
	p11=1;p12=1;
	p21=1;p22=0;
	a11=1;a12=0;
	a21=0;a22=1;
	while(k)
	{
		if(k%2==1)
		{
			b11=(a11*p11+a12*p21)%m;
			b12=(a11*p12+a12*p22)%m;
			b21=(a21*p11+a22*p21)%m;
			b22=(a21*p12+a22*p22)%m;
			a11=b11;a12=b12;a21=b21;a22=b22;
		}
		b11=(p11*p11+p12*p21)%m;
		b12=(p11*p12+p12*p22)%m;
		b21=(p21*p11+p22*p21)%m;
		b22=(p21*p12+p22*p22)%m;
		p11=b11;p12=b12;p21=b21;p22=b22;
		k/=2;
	}
	fout<<a12;
}