#include <iostream>
#include <cstdio>
#define MM 666013

using namespace std;

void copyere(long long int a[5][5], long long int b[5][5])
{
  int i, j;
  for (i=1; i<=2; i++)
    for (j=1; j<=2; j++)
      a[i][j]=b[i][j];
}

void inmult(long long int z1[5][5], long long int z2[5][5], long long int z3[5][5])
{
  long long int aux[5][5];
  int i, j, k;
  for (i=1; i<=2; i++)
    for (j=1; j<=2; j++)
      for (k=1, aux[i][j]=0; k<=2; k++)
        aux[i][j]=(aux[i][j]%MM+(z1[i][k]*z2[k][j])%MM)%MM;
  copyere(z3, aux);
}

void ridput(long long int z1[5][5], long long int k, long long int r[5][5])
{
  while (k)
  {
    if (k%2==0)
    {
      inmult(z1, z1, z1);
      k>>=1;
    }
    k--;
    inmult(r, z1, r);
  }
}

void Elem_neutru(long long int r[5][5])
{
  r[1][1]=r[2][2]=1;
  r[1][2]=r[2][1]=0;
}

long long int Fibo_Term(long long int k)
{
  if (k<=2)
    return 1;
  k-=2;
  long long int z1[5][5]={{0, 0, 0}, {0, 0, 1}, {0, 1, 1}};
  long long int r[5][5];
  Elem_neutru(r);
  ridput(z1, k, r);
  return (r[1][2]+r[2][2])%MM;
}

int main()
{
  long long int k;
  freopen("kfib.in", "r", stdin);
  freopen("kfib.out", "w", stdout);
  scanf("%lld", &k);
  printf("%lld", Fibo_Term(k)%MM);
  return 0;
}