#include <fstream>
#include <vector>
#define vvi std::vector<std::vector<int>>

const int mod = 666013;

int s(int a, int b) { return (a+b)%mod; }
int p(int a, int b) { return (1ll*a*b)%mod; }

vvi multmat(vvi a, vvi b){
	vvi ans;
	ans.resize(a.size());
	for(int i=0;i<a.size();i++){
		ans[i].resize(b[0].size());
		for(int j=0;j<b[0].size();j++)
			for(int k=0;k<b.size();k++)
				ans[i][j] = s(ans[i][j], p(a[i][k], b[k][j]));
	}
	return ans;
}

vvi putlog(vvi a, int k) {
	if(k==0) return {{1, 0}, {0, 1}};
	vvi x = putlog(a, k/2);
	x = multmat(x, x);
	if(k&1) return multmat(a, x);
	return x;
}

int main() {
	std::ifstream fin("kfib.in");
	std::ofstream fout("kfib.out");
	int k;
	fin>>k;
	if(k == 0 or k == 1) { fout<<1; return 0; }
	vvi v;
	v = {{1, 1}};
	vvi fib = {{0, 1}, {1, 1}};
	fib = putlog(fib, k-2);
	v = multmat(v, fib);
	fout<<v[0][1];
}