#include<fstream>
#define mod 666013

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");
long long a,b=1,c=1,m,n=1,p=1,aux[4];;

int main()
{
	int k;
	in>>k;
	for(k=k-2;k!=0;k=k/2)//Parcurgem k incepand cu k-2
	{
		if(k%2==1)//daca k e impar
		{
			aux[1]=(a*m+b*n)%mod;//crestem puterea matricei finale
			aux[2]=(a*n+b*p)%mod;
			aux[3]=(b*n+c*p)%mod;
			a=aux[1];
			b=aux[2];
			c=aux[3];
		}
		aux[1]=(m*m+n*n)%mod;//ridicam la patrat matricea secundara
		aux[2]=(m*n+n*p)%mod;
		aux[3]=(n*n+p*p)%mod;
		m=aux[1];
		n=aux[2];
		p=aux[3];
	}
	out<<c<<"\n";
}