#include <fstream>
using namespace std;
ifstream f("kfib.in"); 
ofstream of("kfib.out");
typedef struct matr{
	long long x, y, z, t;
};
matr nullmatr;
matr inm(const matr&m, const matr&n){
	matr rez;
	rez.x = (((m.x % 666013) * (n.x % 666013)) % 666013 + ((m.y % 666013) * (n.z % 666013)) % 666013) % 666013;
	rez.y = (((m.x % 666013) * (n.y % 666013)) % 666013 + ((m.y % 666013) * (n.t % 666013)) % 666013) % 666013;
	rez.z = (((m.z % 666013) * (n.x % 666013)) % 666013 + ((m.t % 666013) * (n.z % 666013)) % 666013) % 666013;
	rez.t = (((m.z % 666013) * (n.y % 666013)) % 666013 + ((m.t % 666013) * (n.t % 666013)) % 666013) % 666013;
	return rez;
}
matr pow(const matr&m, const int& n){
	if (n == 0)return nullmatr;
	else if (n == 1)return m;
	else if (!(n % 2)) return pow(inm(m, m),n / 2);
	else if (n % 2) return inm(m, pow(inm(m, m), n / 2));
}
int main(){
	matr z; z.x = 0; z.y = z.z = z.t = 1;
	int k;
	f >> k;
	of<<pow(z, k - 1).t;
}