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