//#include "stdafx.h"
#include <fstream>

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

const int modulo = 666013;

struct mat {
	long long m[3][3];
};

mat I2,mat_const,mat_init;

mat inm(mat m1, mat m2) {
	mat m_rez;
	m_rez.m[1][1] = (m1.m[1][1] * m2.m[1][1] + m1.m[1][2] * m2.m[2][1]) % modulo;
	m_rez.m[1][2] = (m1.m[1][1] * m2.m[1][2] + m1.m[1][2] * m2.m[2][2]) % modulo;
	m_rez.m[2][1] = (m1.m[2][1] * m2.m[1][1] + m1.m[2][2] * m2.m[2][1]) % modulo;
	m_rez.m[2][2] = (m1.m[2][1] * m2.m[1][2] + m1.m[2][2] * m2.m[2][2]) % modulo;
	return m_rez;
}

mat lgput(mat m, long long p) {
	if (p == 0) {
		return I2;
	}
	if (p % 2 == 0) {
		mat mk = lgput(m, p / 2);
		return(inm(mk, mk));
	}
	else {
		return inm(m, lgput(m, p - 1));
	}
}

int main(){
	int k;
	I2.m[1][1] = 1;
	I2.m[1][2] = 0;
	I2.m[2][1] = 0;
	I2.m[2][2] = 1;

	mat_const.m[1][1] = 0;
	mat_const.m[1][2] = 1;
	mat_const.m[2][1] = 1;
	mat_const.m[2][2] = 1;

	mat_init.m[1][1] = 0;
	mat_init.m[1][2] = 1;
	mat_init.m[2][1] = 0;
	mat_init.m[2][2] = 0;

	cin >> k;
	if (k == 0) {
		cout << 0;
		return 0;
	}
	cout << inm(mat_init, lgput(mat_const, k - 1)).m[1][2];
    return 0;
}