#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 i2 = {{1, 0}, {0, 1}};

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

vvi putlog(vvi n, int k) {
	if(!k) return i2;
	vvi x = putlog(n, k/2);
	if(k%2==0) return prod(x, x);
	return prod(prod(x, x), n);
}

int main() {
	std::ifstream fin("kfib.in");
	std::ofstream fout("kfib.out");
	int n;
	fin>>n;
	vvi mat = {{0, 1}, {1, 1}}, ans = {{0, 1}};
	mat = putlog(mat, n-1);
	ans = prod(ans, mat);
	fout<<ans[0][1];;
}