#include <bits/stdc++.h>

#define NMAX 10010
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

#define MOD 666013

int n;

typedef unsigned long long  ull;

ull A[3][3];
ull sol[3][3];

void init()
{
   A[0][0] = 0;
   A[0][1] = A[1][0] = A[1][1] = 1;
   sol[0][0] = 0;
   sol[0][1] = sol[1][0] = sol[1][1] = 1;
}

void afisare(ull a[][3])
{
   for(int i=0;i<2;i++)
   {
      for(int j=0;j<2;j++)
         cout<<a[i][j]<<" ";
      cout<<endl;
   }
   cout<<endl;
}

void inm(ull a[3][3],ull b[3][3])
{
   ull aux[3][3];
   aux[0][0] = 0;
   aux[0][1] = aux[1][0] = aux[1][1] = 0;

   for(int i=0;i<2;i++)
   {
      for(int j=0;j<2;j++)
      {

         for(int k=0;k<2;k++)
         {
            aux[i][j] = (aux[i][j]%MOD + a[i][k]%MOD * b[k][j]%MOD) % MOD;
         }

      }
   }

   //afisare(aux);

   for(int i=0;i<2;i++)
      for(int j=0;j<2;j++)
         a[i][j] = aux[i][j];

}

void mult(ull A[][3],ull n)
{
   while(n)
   {
      if(n&1)
         inm(sol,A);
      inm(A,A);
      n>>=1;
   }


}

int main()
{
   fin>>n;

   if(n<=2)
      fout<<1;
   else
   {
      init();
      mult(A,n-2);
      fout<<sol[1][1]<<" ";
   }

}