#include<stdio.h>
using namespace std;
long long poz;
long long fib(int n)
{
	long long x,y;
	if(n==1||n==2) return 1;
	else
	if(n==3) return 2;
	else
	if(n==4) return 3;
	else
	{
		if(n%2==0)
		{
			x=fib(n/2+1);
			y=fib(n/2-1);
			return (x*x-y*y+666013)%666013;
		}
		else
		{
			x=fib(n/2);
			y=fib(n/2+1);
			return ((x*x)%666013+(y*y)%666013)%666013;
		}
	}
}
int main()
{
freopen("kfib.in","r",stdin);
freopen("kfib.out","w",stdout);
scanf("%d",&poz);
printf("%d\n",fib(poz));
return 0;
}