#include<iostream>
#include<fstream>
using namespace std;

typedef long long MAT2[2][2];
MAT2 m3[2];
MAT2 pr[2];
void prod(MAT2 m1,MAT2 m2,MAT2 m3)
{
	int l,c,k;
	for(l=0;l<2;l++)
	{
		for(c=0;c<2;c++)
		{
			m3[l][c]=0;
			for(k=0;k<2;k++)
				m3[l][c]=(m3[l][c] + (m1[l][k]*m2[k][c])%666013)%666013;
		}
	}
}

int pow(int k)
{
	m3[0][0][0]=0;m3[0][0][1]=1;m3[0][1][0]=1;m3[0][1][1]=1;
	pr[0][0][0]=1;pr[0][0][1]=0;pr[0][1][0]=0;pr[0][1][1]=1;
	int t=0,s=0;
	while(k!=1)
	{
		if(k%2==0)
			prod(m3[t%2],m3[t%2],m3[(t+1)%2]),++t,k=k/2;
		else
			prod(m3[t%2],pr[s%2],pr[(s+1)%2]),++s,k--;
	}

	prod(m3[t%2],pr[s%2],m3[(t+1)%2]);

	return m3[(t+1)%2][1][0]; 
}

int main()
{
	ofstream out("kfib.out");
	ifstream in("kfib.in");
	int k;
	in>>k;
	cout<<k;
	if(k==0)
		out<<"0";
	else if(k==1)
		out<<"1";
	else
		out<<pow(k);
	return 0;
}