#include<fstream>
using namespace std;
int n,x,y,m,i,mod=666013;
int main()
{
	ifstream f("kfib.in");
	ofstream g("kfib.out");
	f>>n;
	n=n%(mod*2+2);
	x=1;
	y=1;
	for(i=3;i<=n;i++)
	{
		m=(x+y)%mod;
		x=y;
		y=m;
	}
	g<<y;
}