#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long k;

void inmultire(long long a[2][2], long long b[2][2], long long c[2][2])
{
	for (int i = 0; i <= 1; i++)
	{
		for (int j = 0; j <= 1; j++)
		{
			c[i][j] = 0;
			for (int k = 0; k <= 1; k++)
			{
				c[i][j] += a[i][k] * b[k][j];
				c[i][j] = c[i][j] % MOD;
			}
		}
	}
}
void copiaza(long long a[2][2], long long b[2][2])
{
	for (int i = 0; i <= 1; i++)
	{
		for (int j = 0; j <= 1; j++)
			a[i][j] = b[i][j];
	}
}
int main()
{
	long long a[2][2] = { { 1, 1 }, { 1, 0 } };
	long long b[2][2] = { { 1, 0 }, { 1, 0 } };
	long long c[2][2];
	f >> k;
	k = k - 1;
	while (k != 0)
	{
		if (k % 2 == 1)
		{
			inmultire(b, a, c);
			copiaza(b, c);
		}
		inmultire(a, a, c);
		copiaza(a, c);
		k = k / 2;
	}
	
	g << b[0][0] % MOD;
	return 0;
}