#include <fstream>
#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int n;
long long a[2][2] = { {0,1},{0,0} };
long long c[2][2] = { {0,1},{1,1} };
long long sol[2][2] = { {1,0},{0,1} };
void inmultire(long long a[2][2], long long b[2][2])
{
	long long c[2][2];
	int i, j, k;
	for (i = 0; i <= 1; i++)
	{
		for (j = 0; j <= 1; j++)
		{
			c[i][j] = 0;
			for (k = 0; k <= 1; k++)
				c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
		}
	}

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