#include <bits/stdc++.h>

#define zeros(x) ((x^(x-1))&x)

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int k,a[2][2],sol[2][2],bin[30];
const int mod=666013;

void inmultesc( int v[2][2] )
{
 int nou[2][2];
 nou[0][0]=nou[0][1]=nou[1][0]=nou[1][1]=0;

 for(int i=0;i<2;i++)
  for(int j=0;j<2;j++)
   for(int p=0;p<2;p++)
     nou[i][j]=( nou[i][j]+1LL*a[i][p]*sol[p][j]%mod ) %mod;

 for(int i=0;i<2;i++)
  for(int j=0;j<2;j++)
   sol[i][j]=nou[i][j];
}

void ridic( int v[2][2] )
{
 int nou[2][2];
 nou[0][0]=nou[0][1]=nou[1][0]=nou[1][1]=0;

 for(int i=0;i<2;i++)
  for(int j=0;j<2;j++)
   for(int p=0;p<2;p++)
     nou[i][j]=( nou[i][j]+1LL*v[i][p]*v[p][j]%mod ) %mod;

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

int main()
{
 f>>k;

 if(k==1||k==2){
  g<<'1';
  return 0;
 }
 a[0][0]=0;
 a[0][1]=1;
 a[1][1]=1;
 a[1][0]=1;
 sol[0][0]=sol[1][1]=1;

 k-=2;

 int nr=0,cpy=k;

 while( k )
 {
  if(k%2==1) bin[nr]=1;
  else bin[nr]=0;
  nr++;
  k/=2;
 }

 for(int i=0;i<nr;i++)
 {
  if(bin[i]) inmultesc(a);
  ridic(a);
 }

 g<<(sol[0][1]+sol[1][1])%mod;
}