#include <cstdio>

#define MOD 666013

using namespace std;

int mi[3][3];
int m1[3][3];

inline int inmultire_matrici( int a[3][3], int b[3][3], int p )
{
  int mat[3][3];

  for( int i=1;i<=2;i++ )
    for( int j=1;j<=2;j++ )
    {
      mat[i][j]=0;

      for( int l=1;l<=2;l++ )
        mat[i][j]=(mat[i][j]+1LL*a[i][l]*b[l][j]%MOD)%MOD;
    }

  if( p )
  {
    for( int i=1;i<=2;i++ )
      for( int j=1;j<=2;j++ )
        mi[i][j]=mat[i][j];
  }
  else
  {
    for( int i=1;i<=2;i++ )
      for( int j=1;j<=2;j++ )
        m1[i][j]=mat[i][j];
  }
}

int rpl( int pow )
{
  while( pow )
    if( pow%2==1 )
    {
      inmultire_matrici(m1,mi,1);
      pow--;
    }
    else
    {
      inmultire_matrici(m1,m1,0);
      pow/=2;
    }
}

int main()
{
  freopen( "kfib.in", "r", stdin );
  freopen( "kfib.out", "w", stdout );

  int k;

  scanf( "%d", &k );

  m1[1][2]=m1[2][1]=m1[2][2]=1;
  mi[1][2]=mi[2][2]=1;

  rpl(k-1);

  printf( "%d", mi[1][2] );

  return 0;
}