#include <iostream>
#include <fstream>
#define modu 666013
std::ifstream fin("kfib.in");
std::ofstream fout("kfib.out");

int k;
long long A[2][2];
long long K[2][2];

void copy(long long B[2][2], long long C[2][2])
{
  for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
      B[i][j]=C[i][j];
}

void mult(long long B[2][2], long long C[2][2])
{
  long long D[2][2];
  for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
    {
      D[i][j]=0;
      for(int k=0;k<2;k++)
      {
        D[i][j]+=(B[k][j]*C[i][k])%modu;
        D[i][j]=D[i][j]%modu;
      }
    }
  copy(B,D);
}

int main()
{
  fin>>k;
  A[0][0]=1;
  A[0][1]=1;
  A[1][0]=1;
  copy(K,A);
  int pow2=1;
  k=k-3;
  while(k!=0)
  {
    if((k&pow2)!=0)
    {
      k-=pow2;
      mult(A,K);
    }
    pow2=pow2<<1;
    mult(K,K);
  }
  fout<<(A[0][0]+A[1][0])%modu;
}