#include<fstream>
#define MOD 666013
using namespace std;
using ll = long long;

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


ll z[3][3] =
{
	{1,0,0},
	{0,1,0},
	{0,0,1}
};
ll a[3][3] = {
	{0,0,0},
	{0,0,1},
	{0,1,1}
};
ll m1[3][3] = {
	{0,0,0},
	{0,0,1},
	{0,0,0}
};

void matrix_mult(ll a[][3], ll b[][3], ll c[][3])
{
	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= 2; j++)
			for (int k = 1; k <= 2; k++)
				c[i][j] += (1LL * a[i][k] * b[k][j]) % MOD;
}

void copy_matrix(ll a[][3],ll b[][3])
{
	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= 2; j++)
			a[i][j] = b[i][j];
	
}
void empty_matrix(ll a[][3])
{
	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= 2; j++)
			a[i][j] = 0;
}
void powr(ll a[][3], int n)
{
	
	while (n)
	{
		if (n & 1)
		{
			ll aux[3][3];
			copy_matrix(aux, z);
			empty_matrix(z);
			matrix_mult(aux, a, z);
			
		}

		ll aux[3][3];
		empty_matrix(aux);
		matrix_mult(a, a, aux);
		copy_matrix(a, aux);
		
		n >>= 1;
	}
}

int main()
{
	
  ll res[3][3];
  empty_matrix(res);
  int k;
  f >> k;
  if (k <= 1)
  {
	  g<< k;
	  return 0;
  }
  powr(a, k - 1);
  matrix_mult(m1, z, res);
  g << res[1][2];
	

}