#include<fstream>
#include<algorithm>
#include<map>
#define LL long long
using namespace std;

const LL MOD=666013; 

LL n;
map<LL,LL> Fib;

LL f(LL x) {
	if(Fib.count(x)) return Fib[x];
	LL k=x/2;
	if(x%2) return Fib[x]=(f(k)*f(k+1) + f(k-1)*f(k))%MOD;
	else return Fib[x]=(f(k)*f(k) + f(k-1)*f(k-1))%MOD;
}

int main()
{
  ifstream cin("kfib.in");
  ofstream cout("kfib.out");

  cin>>n; Fib[0]=Fib[1]=1;
  cout<<f(n-1)<<'\n';

 return 0;
}