#include <iostream>
#include <fstream>
using namespace std;
#define mod 666013
long long n, solutie[2][2], z[2][2];
void inmulteste(long long p[2][2],long long q[2][2],long long r[2][2])
{long long c[2][2];
	c[0][0]=(p[0][0]*q[0][0]) % mod+(p[0][1]*q[1][0]) % mod;
	c[0][1]=(p[0][0]*q[0][1]) % mod+(p[0][1]*q[1][1]) % mod;
	c[1][0]=(p[1][0]*q[0][0]) % mod+(p[1][1]*q[1][0]) % mod;
	c[1][1]=(p[1][0]*q[0][1]) % mod+(p[1][1]*q[1][1]) % mod;
	r[0][0]=c[0][0];
	r[0][1]=c[0][1];
	r[1][0]=c[1][0];
	r[1][1]=c[1][1];
} 
void imparte(long long p[2][2])
{
	p[0][0]=p[0][0] % mod;
	p[0][1]=p[0][1] % mod;
	p[1][0]=p[1][0] % mod;
	p[1][1]=p[1][1] % mod;
}
void putere(long long a)
{ 
	for(;a;a=a/2)
	{
		if (a %2==1)
			{ 
				inmulteste(solutie,z,solutie);   
				imparte(solutie);
		}
		inmulteste(z,z,z);
		imparte(z);
	}
}
int main()
{
	ifstream f("kfib.in");
	f>>n;
	z[0][0]=0;
	z[0][1]=1;
	z[1][0]=1;
	z[1][1]=1;
	solutie[0][0]=1;
	solutie[0][1]=0;
	solutie[1][0]=0;
	solutie[1][1]=1;
	putere(n-1);
	ofstream g("kfib.out");
	g<<solutie[1][1];
	return 0;

}