#include <fstream>
#define MOD 666013
using namespace std;
typedef struct{
int 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=((((long long)x.a*y.a)%MOD)+(((long long)x.b*y.c)%MOD))%MOD;
	m.b=((((long long)x.a*y.b)%MOD)+(((long long)x.b*y.d)%MOD))%MOD;
	m.c=((((long long)x.c*y.a)%MOD)+(((long long)x.d*y.c)%MOD))%MOD;
	m.d=((((long long)x.c*y.b)%MOD)+(((long long)x.d*y.d)%MOD))%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;
}