/*
	http://www.infoarena.ro/problema/kfib
*/

#define INPUT "kfib.in"
#define OUTPUT "kfib.out"

#define MOD 666013

#include <fstream>
#include <iostream>
using namespace std;

int K, first, second, m[2][2];

void setup()
{
	first = 1;
	second = 1;
	m[0][0] = 1;
	m[0][1] = 1;
	m[1][0] = 1;
	m[1][1] = 0;
}

void read()
{
	ifstream fin(INPUT);
	fin >> K;
	fin.close();
}

void multiply()
{
	int x = first * m[0][0] + second * m[1][0];
	int y = first;
	first = x % MOD;
	second = y % MOD;
}

void solve()
{
	for (int i = 1; i < K - 1; ++i)
	{
		multiply();
	}
}

void write(int solution)
{
	ofstream fout(OUTPUT);
	fout << solution << "\n";
	fout.close();
}

int main(void)
{
	read();
	if (K == 0)
	{
		write(0);
	}
	else if (K == 1 || K == 2)
	{
		write(1);
	}
	else
	{
		setup();
		solve();
		write(first);
	}
	return 0;
}