#include <fstream>
using namespace std;
typedef long unsigned lu;
lu m=666013;

lu f(lu n){
	if (n==0) return 0;
	if (n<3) return 1;
	lu k;
	if (n%2==0){
		k=n/2;
		lu fk=f(k);
		return ((2*f(k-1)+fk)*fk)%m;
	}
	if (n%2){
		k=(n+1)/2;
		lu fk=f(k), fk1=f(k-1);
		return (fk*fk+fk1*fk1)%m;
	}
	return 0;
}
		

int main()
{
	ifstream cin("kfib.in");
	ofstream cout("kfib.out");
	lu n;
	cin>>n;
	cout<<f(n);
/*	cin.close();
	cout.close();*/
	return 0;
}