// Include
#include <fstream>
#include <cstring>
using namespace std;

// Definitii
#define ll long long

// Constante
const int mod = 666013;

// Functii
void multiply1(int A[3][3], int B[3][3]);
void multiply2(int A[3][3]);

// Variabile
ifstream in("kfib.in");
ofstream out("kfib.out");

int power;
int number[3][3], answer[3][3];

// Main
int main()
{
	in >> power;
	--power;
	
	answer[1][1] = 1;	answer[2][1] = 0;
	answer[1][2] = 0;	answer[2][2] = 1;
	
	number[1][1] = 0;	number[2][1] = 1;
	number[1][2] = 1;	number[2][2] = 1;
	
	for(int i=0 ; (1<<i)<=power ; ++i)
	{
		if((1<<i) & power)
			multiply1(answer, number);
		
		multiply2(number);
	}
	
	out << answer[2][2];
	
	in.close();
	out.close();
	return 0;
}

void multiply1(int A[3][3], int B[3][3])
{
	int C[3][3];
	memcpy(C, A, sizeof(C));
	
	A[1][1] = ((ll)B[1][1] * (ll)C[1][1] + (ll)B[1][2] * (ll)C[2][1]) % mod;
	A[1][2] = ((ll)B[1][1] * (ll)C[1][2] + (ll)B[1][2] * (ll)C[2][2]) % mod;
	A[2][1] = ((ll)B[2][1] * (ll)C[1][1] + (ll)B[2][2] * (ll)C[2][1]) % mod;
	A[2][2] = ((ll)B[2][1] * (ll)C[1][2] + (ll)B[2][2] * (ll)C[2][2]) % mod;
}

void multiply2(int A[3][3])
{
	int C[3][3];
	memcpy(C, A, sizeof(C));
	
	A[1][1] = ((ll)C[1][1] * (ll)C[1][1] + (ll)C[1][2] * (ll)C[2][1]) % mod;
	A[1][2] = ((ll)C[1][1] * (ll)C[1][2] + (ll)C[1][2] * (ll)C[2][2]) % mod;
	A[2][1] = ((ll)C[2][1] * (ll)C[1][1] + (ll)C[2][2] * (ll)C[2][1]) % mod;
	A[2][2] = ((ll)C[2][1] * (ll)C[1][2] + (ll)C[2][2] * (ll)C[2][2]) % mod;
}