#include<fstream>
#include<iostream>
using namespace std;
#define mod 666013
long long k;
long long fact(long long nr){
	long long x,y,z;
	if(nr==1)
		return 1;
	if(nr==2)
		return 1;
	if(nr==0)
		return 0;
	if(nr==3)
		return 2;
	if(nr==4)
		return 3;
	
	if(nr%2==0){
		
		x=fact(nr/2)%mod;
		y=fact(nr/2-1)%mod;
		z=(x+y)%mod;
		
		return ((x*y)+(x*z))%mod;
	}
	else{
		x=fact(nr/2)%mod;
		y=fact(nr/2+1)%mod;
		
		return ((x*x)+(y*y))%mod;
	}
}
int main(){
	ifstream f("kfib.in");
	ofstream g("kfib.out");
	f>>k;
	g<<fact(k);
	return 0;
}