#include <stdio.h>
#define dim 4

using namespace std;

FILE *f=fopen("kfib.in","r"), *g=fopen("kfib.out","w");

int i,a[dim][dim],b[dim][dim],exp;

void Inmultire(int a[4][4], int b[4][4])
{
  int c[4][4];
  for(int i=1; i<=2; i++)
   for(int j=1; j<=2; j++)
    c[i][j]=0;

  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]%666013;

 for(int i=1;i<=2; i++)
  for(int j=1; j<=2; j++)
   a[i][j] = c[i][j]%666013;
}



int main()
{

 fscanf(f,"%d",&exp);
 exp--;

 for(i=1; i<=2; i++)
 a[i][i] = 1;

 b[1][2] = b[2][1] = b[2][2] = 1;


 for(i=0; i<=31; i++)
  {if(exp & (1<<i) )
   Inmultire(a,b);

   Inmultire(b,b);
  }

fprintf(g,"%d",a[2][2]);


return 0;
}