/*
	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, solution;
long long m[2][2], fib[2][2];

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

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

void multiply()
{
	int a, b, c, d;
	a = (fib[0][0] * m[0][0] + fib[0][1] * m[1][0]) % MOD;
	b = (fib[0][0] * m[0][1] + fib[0][1] * m[1][1]) % MOD;
	c = (fib[1][0] * m[0][0] + fib[1][1] * m[1][0]) % MOD;
	d = (fib[1][0] * m[0][1] + fib[1][1] * m[1][1]) % MOD;
	fib[0][0] = a;
	fib[0][1] = b;
	fib[1][0] = c;
	fib[1][1] = d;
}

void solve()
{
	for (int i = 1; i < K - 1; ++i)
	{
		multiply();
	}
	solution = fib[0][0];
}

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

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