#include <fstream>
#include <map>
typedef long long ll;
#define mod 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int K;
map<ll,ll> M;
ll f(ll k){
	if(M[k] != 0) return M[k];
	else return M[k] = (f((k+1)/2)*f(k/2) + f((k-1)/2)*f((k-2)/2))%mod;
}
int main(){
	fin >> K;
	M[0] = M[1] = 1;
	fout << f(K-1);
	
	return 0;
}