#include<fstream.h>
#include<iostream.h>

long long n,m00,m01,m10,m11,s00,s01,s10,s11,i,p=666013,a,b,c,d;

int main()
{
	ifstream f("kfib.in");
	ofstream g("kfib.out");
	f>>n;
	m00=0;
	m01=m10=m11=1;
	s00=s11=0;
	s01=s10=1;
	for(i=0;(1<<i)<=n;i++)
	{	
		if((1<<i)&n)
		{
			a=(s00*m00%p+s01*m10%p)%p;
			b=(s00*m01%p+s01*m11%p)%p;
			c=(s10*m00%p+s11*m10%p)%p;
			d=(s10*m01%p+s11*m11%p)%p;
			s00=a;
			s01=b;
			s10=c;
			s11=d;
		}
		a=(m00*m00%p+m01*m10%p)%p;
		b=(m00*m01%p+m01*m11%p)%p;
		c=(m10*m00%p+m11*m10%p)%p;
		d=(m10*m01%p+m11*m11%p)%p;
		m00=a;
		m01=b;
		m10=c;
		m11=d;
	}
	g<<s11;
	return 0;
}