#include<bits/stdc++.h>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define mod 666013
long long n;
map<long long,long long > fib;
long long f(long long x){

if(gib.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()
{
	cin>>n;
	fib[0]=fib[1]=1;
	cout<<f(n-1)<<"\n";
	
	
	return 0;
}