#include <fstream>
#define MOD 666013
using namespace std;
typedef struct{
long long a,b,c,d;
}elem;
int n;
elem lgput(elem m,int put)
{
	elem x,y;
	if(put==1) return m;
	if(put%2)
	{
		x=lgput(m,put-1);
		y=m;
	} else
	{
		x=lgput(m,put/2);
		y=x;
	}	
	m.a=((x.a*y.a)+(x.b*y.c))%MOD;
	m.b=((x.a*y.b)+(x.b*y.d))%MOD;
	m.c=((x.c*y.a)+(x.d*y.c))%MOD;
	m.d=((x.c*y.b)+(x.d*y.d))%MOD;
	return m;
}
int main()
{
	elem m;
	ifstream fi("kfib.in");
	ofstream fo("kfib.out");
	fi>>n;
	m.a=0; m.b=1; m.c=1; m.d=1; 
	m=lgput(m,n-1);
	fo<<m.d%MOD<<"\n";
	return 0;
}