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

lu f(lu n){
	if (n==0) return 0;
	if (fib[n]) return fib[n];
	lu k;
	if (n%2==0){
		k=n/2;
		if (fib[k]==0) fib[k]=f(k);
		if (fib[k-1]==0) fib[k-1]=f(k-1);
		return ((2*fib[k-1]+fib[k])*fib[k])%m;
	}
	if (n%2){
		k=(n+1)/2;
		if (fib[k]==0) fib[k]=f(k);
		if (fib[k-1]==0) fib[k-1]=f(k-1);
		return (fib[k]*fib[k]+fib[k-1]*fib[k-1])%m;
	}
}
		

int main()
{
	ifstream cin("kfib.in");
	ofstream cout("kfib.out");
	fib[1]=fib[2]=1;
	lu n;
	cin>>n;
	cout<<f(n);
	cin.close();
	cout.close();
	return 0;
}