#include<fstream>
#include<algorithm>
#include<map>
using namespace std;

const int MOD=666013; 

long long n;
map<long long,long long> Fib;

long long f(long long x) {
	if(Fib.count(x)) return Fib[x];
    return Fib[x]=(f((x+1)/2)*f(x/2)+f((x-1)/2)*f((x-2)/2))%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;
}